Магазин производит закупку болтов (
bolt), гаек (
nut), гвоздей (
pin), шайб (
shim) и винтов (
screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество двух различных изделий, нужно выбрать тот способ, при котором будет куплено как можно больше болтов.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством других товаров, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено болтов и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов, гаек, гвоздей, шайб и винтов у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия. Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных болтов, затем оставшуюся неиспользованной сумму денег. (в одной строке через один пробел)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 1650
600 screw
750 bolt
750 shim
450 pin
300 nut
150 bolt |
2 0 |