Archive - Маршрутка

Маршрутка ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 50, 1 ≤ P ≤ 20

0 ≤ K_i < P, i < d_i,j ≤ N

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

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