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

Input file name: bank.in
Output file name: bank.out
Time limit: 1 s
Memory limit: 32 megabytes

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

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

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

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

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

Пример:

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


Source: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Discuss       Submit a solution



Printable version