Магазин производит закупку болтов (
bolt) и гаек (
nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:
- Нужно купить как можно больше изделий, независимо от их типа и модификации.
- Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше гаек.
- Если можно разными способами купить максимальное количество изделий с одинаковым количеством гаек, нужно выбрать тот способ, при котором вся покупка будет дешевле.
Определите, сколько всего будет куплено гаек и какая сумма останется неиспользованной.
Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.
Выходные данные
В ответе запишите два целых числа: сначала количество закупленных гаек, затем оставшуюся неиспользованной сумму денег.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6500
1500 bolt
500 bolt
3500 nut
3000 nut
2500 bolt
1000 nut |
2 500 |