Сортировки

Магазин «1000 мелочей» закупает у поставщика продукцию для дальнейшей перепродажи. Известно количество товаров на складе у поставщика и стоимость каждого из них. К сожалению, бюджет магазина ограничен, поэтому принято решение закупить как можно больше товаров на ту сумму, которой располагает магазин. По заданной информации о цене каждого товара и бюджете магазина, определите

1) максимальную возможную стоимость товара, который можно купить при условии, что закупили максимально возможное количество товаров;

2) количество купленных товаров, у которых минимальная цена.

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

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

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

100 9

20

30

20

5

10

15

10

30

10

В данном примере можно закупиться следующим образом: 5 10 10 10 15 20 20, либо 5 10 10 10 15 20 30. в первом случае максимальная сумма 20, во втором 30, а общее количество 7. В ответе нужно указать: 30 1.