0147. Вовочка и ограбление банка

Имя входного файла:	bank.in
Имя выходного файла:	bank.out
Ограничение по времени:	1 s
Ограничение по памяти:	32 megabytes

Вовочка с другом бегут в соседний банк, ведь у друга Вовочки откуда-то уже есть ключи (или отмычки) от всех замков главного сейфа. Более того, у Вовочки есть план сейфа. Ведь сейф-то необычный! Он и не сейф вовсе! За дверью находятся несколько коридоров, где лежат мешки с деньгами. Чтобы доползти по коридору до мешка, Вовочке требуется некоторое время. В разных мешках может быть разное количество денег. Разные мешки удалены на разные расстояния или находятся в разных коридорах. Ребята не умеют снимать сигнализацию, поэтому им надо успеть скрыться от полиции. Для этого Вовочке надо успеть выйти из деньгохранилища не позднее, чем в момент Т. За единицу времени Вовочка преодолевает единицу расстояния. Какова максимальная сумма денег, которую Вовочка с другом могут наворовать?

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

На первой строке входного файла число 1 ≤ К ≤ 100 - количество коридоров и число 1 ≤ Т ≤ 600. Далее - описания коридоров. В первой строке описания √ количество мешков М в этом коридоре. В М следующих строках - по 2 числа. Первое √ расстояние до мешка, не более 30000, второе √ количество денег в мешке, не более 60000. Все числа √ целые неотрицательные. В одной точке не лежат два мешка одновременно. Всего мешков не более 30000.

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

Вывести надо максимально возможную награбленную сумму.

Пример:

bank.in	bank.out
4 12 3 1 2 7 3 9 1000 2 3 4 4 1 0 1 6 6	7

Источник: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Обсудить       Отправить решение



Версия для печати