Сортировки
Магазин «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.
