Задача #6715

Для перевозки партии грузов различной массы выкупают место у компании перевозчиков. Компания перевозчик не может принять на борт больше S тонн груза. Известно, что отдельный груз нельзя разделить для перевозки, то есть один груз должен доставляться одним рейсом на одном грузовом судне. Так же преследуют тактику – перевезти рейсом грузы как можно большей массы.

За какое минимальное количество рейсов можно перевезти все грузы?

Входные данные представлены в файле следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество грузов и S – грузоподъёмность грузового судна в тоннах. Каждая из следующих N строк содержит одно целое число < S – массу груза в тоннах.

В ответе запишите два числа – минимальное количество рейсов и суммарную массу грузов, которые будут перевезены последним рейсом.

Пример организации исходных данных во входном файле:

6 500

140

150

160

200

220

240

При таких входных данных ответ будет 3 и 150.

Первым рейсом будет отправлено 2 груза – 240 и 220, вторым – 200, 160 и 140, третьим – 150.