Маршрутка

Автор:unknown   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Маршрутное такси на P посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров. Каждый пассажир имеет цель — попасть на некоторую остановку, расположенную дальше по маршруту.

На каждой остановке:

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

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

В первой строке входного файла содержатся числа N и P. В следующих N − 1 строках находятся числа Ki di,1… di,Ki — количество пассажиров на очередной остановке и цель каждого пассажира. (На конечной остановке пассажиры не садятся).

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

Выходной файл должен содержать единственное целое число — максимальный доход водителя в рублях.

Ограничения

2 ≤ N ≤ 50, 1 ≤ P ≤ 20

0 ≤ Ki < P, i < di,j ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
2 2 4
3 3 3 3
2 4 4
30

0.039s 0.007s 15