Задача 2 из 21

Посылки по очереди

Время 2 с · память 256 МБ

На складе находятся NN посылок, которые грузят в автомобиль грузоподъёмностью SS. Сначала в автомобиль кладут самую тяжёлую посылку из тех, что помещаются, затем — самую лёгкую из оставшихся, затем снова самую тяжёлую из тех, что помещаются, снова самую лёгкую из оставшихся и так далее.

Погрузка заканчивается, когда ни одна из оставшихся посылок не помещается. Посылку, масса которой равна оставшейся грузоподъёмности, погрузить можно. Посылки одинаковой массы считаются разными. Определите количество погруженных посылок и массу посылки, погруженной последней.

Входные данные

В первой строке находятся два натуральных числа: NN — количество посылок (N≤100 000N \le 100\,000) и SS — грузоподъёмность автомобиля (S≤109S \le 10^9). В каждой из следующих NN строк находится масса одной посылки — натуральное число, не превышающее 10 00010\,000.

Массы идут в произвольном порядке и могут повторяться. Гарантируется, что хотя бы одна посылка помещается в автомобиль.

Выходные данные

Выведите два целых числа: сначала количество погруженных посылок, затем массу посылки, погруженной последней.

Примеры

Ввод 1
4 17
10
8
5
4
Вывод 1
2 4
Ввод 2
5 20
9
7
12
3
5
Вывод 2
3 5

Примечание

В первом примере сначала грузят посылку массой 10, затем посылку массой 4. Оставшаяся грузоподъёмность равна 3, и посылки массами 5 и 8 не помещаются.

Во втором примере грузят посылки массами 12, 3 и 5. Третья посылка помещается, потому что её масса равна оставшейся грузоподъёмности. Посылки массами 7 и 9 не помещаются.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче

Посылки по очереди — задание 26 ЕГЭ по информатике