Задача #6705

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

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

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

В первой строке входного файла находятся два числа: S – грузоподъёмность судна (натуральное число, не превышающее 100 000) и N – количество контейнеров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

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

100 4

80

30

50

40

При таких исходных данных можно транспортировать за один раз максимум 2 контейнера. Минимальная грузоподъемность одного катера будет 130.

2 130