Рабочее место участника

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

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

Первая строка ввода содержит три целых числа: количество настроек оборудования `K` (`1\ ≤\ K\ ≤\ 10`), продолжительность рабочего дня в минутах `T` (`100\ ≤\ T\ ≤\ 1000`) и количество дней `N` (`1\ ≤\ N\ ≤\ 1000`). Далее следует `K` строк, описывающих виды продукции, которые можно изготовить при соответствующей настройке оборудования. Сначала в строке указывается количество видов продукции `M_i` (`1\ ≤\ M_i\ ≤\ 10`), затем следует `M_i` пар целых чисел: время изготовления в минутах `W_{ij}` (`1\ ≤\ W_{ij}\ ≤\ 10000`) и прибыль от продажи этого изделия `P_{ij}` (`1\ ≤\ P_{ij}\ ≤\ 1000000`).

В первой строке вывести одно число — максимальную прибыль, которую можно получить за `N` дней работы мастерской.

2 300 5 
2 1000 10000 900 5000
2 50 10 170 1000

11020