Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






C. Боремся с гиподинамией

Задачу добавил: alef

Успешно сдано решений: 5

ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Программист ведет малоподвижный образ жизни и не так давно стал понимать, что его это не устраивает. Для начала он решил побольше ходить пешком. Однако расстояние от его дома до работы очень невелико, а «просто гулять» он не любит. Поэтому каждый раз старается придумать, зачем он гуляет.

Сегодня он решил проложить маршрут по магазинам, поскольку ему надо приобрести кое-какие продукты и хозтовары — всего M наименований. Программист не любит носить в руках пакеты, и хочет все свои приобретения сложить в рюкзак. Рюкзак у него не очень большой, поэтому Программист заранее продумал, как сложить купленное так, чтобы донести всё до дома в целости и сохранности.

Кроме того, Программист пришел к выводу, что нужно покупать товары в строго определенной последовательности — чтобы не было необходимости несколько раз вытаскивать все из рюкзака и складывать заново. Так что теперь у него есть список товаров T1, T2,... , TM (ради простоты будем считать, что наименования товаров заменены целыми числами).

Есть N магазинов, в каждом из которых присутствует какой-то поднабор (или даже всё из) того, что задумал купить Программист. Программист планирует действовать следующим образом. Сначала он отправится в один из магазинов, где продается первый товар (T1) из его списка. Если в этом магазине также продаются товары T2, T3, ... , Tj, а товар Tj + 1 отсутствует, то Программист приобретет все товары до Tj включительно, а затем отправится в один из магазинов, в котором сможет найти товар Tj + 1. В следующем магазине он вновь будет пополнять свой рюкзак товарами по списку — пока ему не встретится отсутствующий товар, для приобретения которого он отправится в другой магазин.

Так он будет поступать до тех пор, пока не приобретет последний товар из своего списка.

Теперь Программиста заинтересовал вопрос — какое максимальное количество товаров при таком подходе он может приобрести за одно посещение магазина.

Заметим, что Программист может возвращаться в один и тот же магазин несколько раз.

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

В первой строке содержатся целые числа M и N (1 ≤ M, N,  ≤ 105) через пробел — количество товаров в списке Программиста, и количество магазинов соответственно.

Товары нумеруются в соответствии с порядком в списке программиста (Ti = i).

Каждая из следующих N строк содержит целое число Qk — количество товаров (из списка Программиста), имеющихся в наличии в магазине k, за которым через пробел следует Qk целых чисел — номера этих товаров.

Гарантируется, что каждый товар есть хотя бы в одном магазине. Суммарное количество товаров во всех магазинах не превосходит 200000.

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

В первой строке содержится единственное целое число — максимальное количество товаров, которые Программист может приобрести за одно посещение магазина.

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

Входные данные
10 3
4 1 2 3 4
0
6 5 6 7 8 9 10
Выходные данные
6
Входные данные
10 5
4 1 2 3 4
3 1 2 3
6 2 3 4 5 6 10
2 1 9
2 7 8
Выходные данные
5

Сдать задачу

Задать вопрос жюри по этой задаче