После праздника (30 баллов)

Гости разошлись, подарки разложены… Надо еще убрать со стола. Маша сложила всю посуду в несколько стопок и собралась отнести их на кухню.

Однако при переноске посуды таким образом то, что лежит сверху, может и разбиться.

Ваша задача - во-первых, определить, сколько посуды Маша точно донесет до кухни, если понесет уже сложенные стопки, и, во-вторых, сколько (минимально) нужно сформировать дополнительных стопок, чтобы донести до кухни всю посуду в целости и сохранности.

Стопку можно донести до кухни целой, если высота, на которой находится центр тяжести самого верхнего предмета, не превышает некоторой заранее заданной «безопасной» высоты. Ради простоты будем считать, что центр тяжести любого предмета расположен в плоскости, разделяющей этот предмет по высоте точно пополам.

Формирование дополнительных стопок происходит так: с существующих стопок снимаются верхние предметы до тех пор, пока высота стопки не станет «безопасной». Снятые предметы складываются в новые стопки наиболее оптимальным образом.

Примечание.

Считайте, что, когда предметы складывают в стопки, то уменьшения высоты за счет вложения предметов друг в друга не происходит, и высота стопки в точности равна сумме высот предметов, ее составляющих.

Формат входного файла input.txt

Первая строка - три целых числа P, S и H через пробел.

P - количество видов посуды, 0<=P<=10;

S - количество уже сложенных стопок посуды 0 <= S <= 10;

H - «безопасная» высота в сантиметрах, 0<=H<=100;

Следующие Pстрок записаны в формате: символ (прописная латинская буква, обозначающая предмет), за которым через пробел указано целое число - высота предмета в сантиметрах.

Следующие за ними S строк описывают стопки посуды (одна строка - описание одной стопки). Каждая строка содержит прописные латинские буквы через пробел, соответствующие предметам, сложенным в стопку. Первая буква отвечает предмету, который находится в самом низу стопки. Всего букв в каждой строке не более 100.

Формат выходного файла output.txt

Первая строка - два целых числа через пробел. Первое число - количество предметов, которые будут принесены на кухню в целости при существующей раскладке посуды по стопкам; второе число - минимально возможное количество дополнительных стопок, которые нужно сформировать, чтобы донести всю посуду до кухни целой

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

2 1 50

C 12

S 2

S S C S C C S C

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

8 0

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

2 1 50

C 12

S 2

S S C S C C C S

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

7 1