Задание №26

Предприятие производит закупку изделий A и B, на которую выделена определённая сумма денег. У поставщика есть в наличии различные модификации этих изделий по различной цене. При покупке необходимо руководствоваться следующими правилами:

1. Нужно купить как можно больше изделий, независимо от их типа и модификации.

2. Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше изделий A.

3. Если можно разными способами купить максимальное количество изделий с одинаковым количеством изделий A, нужно выбрать тот способ, при котором вся покупка будет дешевле.

Определите, сколько всего будет куплено изделий A и какая сумма останется неиспользованной.

Входные данные

Первая строка входного файла содержит два целых числа: N – общее количество изделий у поставщика и M – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и символ (латинская буква A или B), определяющий тип изделия. Все данные в строках входного файла отделены одним пробелом.

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

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

6 130
30 B
50 B
60 A
20 A
70 A
10 B

В данном случае можно купить не более 4 изделий, из них не более 2 изделий A. Минимальная цена такой покупки 120 руб. (покупаем изделия 30B, 60A, 20A, 10B). Останется 10 руб. В ответе надо записать числа 2 и 10.