Для некоторого предприятия требуется закупить большое количество различных электронных компонентов. На рынке имеется множество предложений по различным компонентам, каждый из которых имеет какую-то цену. Для закупки предприятие выделяет средства таким образом, чтобы купить все возможные компоненты и при этом купить как можно больше каждого из них, но не потратить на каждый тип более, чем определённую сумму денег S. Нужно определить, сколько всего компонентов удастся купить при таких условиях и какая наименьшая общая сумма денег будет на это потрачена.
Входные данные:
В первой строке входного файла находится два числа через пробел: число N - количество компонентов на рынке (натуральное число, не превышающее 10000) и число S - сумма денег, не больше которой можно потратить на каждый тип электронных компонентов (натуральное число, не превышающее 108). В следующих N строках находятся по два числа через пробел: тип электронного компонента (натуральное число, не превышающее 109) и его цена (натуральное число, не превышающее 105).
Известно, что компонентов каждого вида на рынке не бывает более тысячи.
Запишите в ответе два числа: наибольшее общее количество компонентов, которые удастся купить при данных условиях, и наименьшую общую сумму денег, которую им на это нужно будет потратить.
Пример входного файла:
7 12
150 8
237 3
150 4
237 5
237 5
150 3
150 3
При таких исходных данных имеется всего два вида компонентов ("150" и "237")
Компонентов вида "150" можно купить три штуки (за 3, 3 и 4)
Компонентов вида "237" можно купить две штуки (за 3 и 5)
Поэтому ответ для приведённого примера
5 18
