409550: GYM103630 B Рудольф и игра

B. Рудольф и играограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

В конце игры вашу армию ждет штурм вражеской крепости. Для выполнения этого задания вам необходимо выстроить пирамиду из солдат вашей армии. Пирамида строится по следующему принципу. На вершине пирамиды находится некоторое количество солдат $$$P (P \ge 1)$$$. Уровнем ниже может стоять ровно на $$$X (X \ge 1)$$$ cолдата больше. Пирамида строится до тех пор, пока в армии есть солдаты. При этом значения $$$P$$$ и $$$X$$$ выбираются так, чтобы все солдаты армии были задействованы.

Если пирамида будет достаточно высокой, то хотя бы один солдат вашей армии сможет преодолеть стену вражеской крепости и открыть ворота для всей армии.

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

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 20$$$) — количество блокпостов текущего уровня игры.

Далее следует $$$N$$$ строк — описания блокпостов.

Каждая строка описания содержит цифру $$$1$$$, если это описание блокпоста союзников, и $$$2$$$, если это описание вражеского блокпоста. Далее следует целое число $$$M_i$$$ ($$$1 \le M_i \le 100$$$) — количество дверей $$$i$$$-го блокпоста. Далее в той же строке следует $$$M_i$$$ целых чисел $$$A_j$$$ ($$$0 \le A_j \le 2500$$$) — количество солдат за $$$j$$$-й дверью.

Выходные данные

Выведите единственное целое число — максимальную высоту пирамиды, которую сможет построить Рудольф.

ПримерыВходные данные

5
1 3 10 1 20
2 2 5 0
2 2 10 10
1 2 0 5
1 2 0 0

Выходные данные

4

Входные данные

5
1 3 10 1 20
2 2 30 40
2 2 10 10
1 2 0 5
1 2 0 0

Выходные данные

0