C. Боремся с гиподинамией
Задачу добавил: alef
Успешно сдано решений: 5
Программист ведет малоподвижный образ жизни и не так давно стал понимать, что его это не устраивает. Для начала он решил побольше ходить пешком. Однако расстояние от его дома до работы очень невелико, а «просто гулять» он не любит. Поэтому каждый раз старается придумать, зачем он гуляет.
Сегодня он решил проложить маршрут по магазинам, поскольку ему надо приобрести кое-какие продукты и хозтовары — всего 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