Задача #2867

(М. Попков) В далеком королевстве существует волшебный молокозавод, где гномы производят самое вкусное молоко. Волшебный молокозавод произвел крупную поставку самого вкусного молока, которое требуется отправить на продажу с помощью магического поезда. Всё молоко было разлито по бидонам, количество и масса каждого известны. У поезда имеется ограничение по массе груза, который он может увезти за раз, оно также известно.

Помогите гномам отправить на поезде самое вкусное молоко. По заданной информации о массе бидонов и общей массе, которую волшебный поезд может увезти за один раз, определите наибольшее количество бидонов, которое он сможет увезти.

Также определите количество бидонов, которые заведомо не сможет увезти поезд, при условии, что количество погруженных бидонов наибольшее.

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

В первой строке входного файла находятся два числа: M – максимальная масса, которая может быть погружена на поезд (натуральное число, не превышающее 10000) и N – количество бидонов (натуральное число, не превышающее 1000). В следующих N строках находятся массы всех имеющихся бидонов (все числа натуральные, не превышающие 200), каждое в отдельной строке.

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

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

300 4

200

110

150

120

При таких исходных данных можно погрузить максимум два бидона. Возможные массы этих двух бидонов 110 и 120, 110 и 150 или 120 и 150. Заведомо поезд не сможет увезти один бидон с массой 200, поэтому ответ для приведённого примера: 2 1.