Задание

Во Дворце творчества молодёжи и школьников работают 8 кружков технического и художественного направлений. Руководители этих кружков направили администратору заявки на покупку материалов для создания проектов. Получился список, в первой строке которого общее количество проектов N и сумма, выделенная на финансирование всех проектов M. В последующих N строках — стоимость материалов для проекта и литера, обозначающая название кружка: A, B, C, D, E, F, G, H.

Необходимо на выделенную сумму обеспечить материалами как можно большее количество проектов. Если можно разными способами оплатить материалы, то нужно выбрать способ, при котором будет оплачено как можно больше проектов для кружка D. Если при этих условиях есть несколько способов покупки материалов, то нужно выбрать такой, чтобы потратить меньшее количество средств.

Для ответа определи, сколько всего будет оплачено проектов для кружка D и оставшуюся сумму.

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

18 30

9

D

1 A

6 C

7 F

9 E

5 A

9 B

8 G

3 E

7 H

6 A

8 C

3 G

7 H

6 A

5 B

9 A

8 G

Для данного примера можно оплатить не более 7 проектов, из них 0 проектов кружка D. Минимальная цена такой покупки 29 руб. (оплачиваем проекты 1A, 3E, 3G, 5A, 5B, 6A, 6A). Останется 1 руб. В ответе надо записать числа 0 и 1.

Данные для решения задачи находятся в файле 1_1_ost.txt.

Ответ:    ,    .