06. Гирлянды

Школьники из деревни Северная Сиянка решили спаять для всех односельчан ёлочные гирлянды из лампочек. Лампочек у ребят бесконечно много, много у них и цветного лака для их покраски – есть лаки С цветов.

Юные северносиянцы отнеслись к сборке гирлянд вдумчиво, не поленились провести до начала работы кое-какие исследования, в ходе которых были сформулированы Правила следования лампочек: для каждого цвета лампочки был сформирован перечень цветов, которых могла бы быть следующая за ней лампочка. К примеру, за красной уместна только фиолетовая, за зелёной – зелёная, фиолетовая, оранжевая… Будем считать, что цвета пронумерованы: 0, 1, 2, …С-1.

Было решено для каждого из N жителей деревни сделать уникальную гирлянду – не такую, как у соседа. При этом все гирлянды должны быть одинаковой длины и выстроены по Правилам.

Какой должна быть минимальная длина гирлянды? Гарантируется, что решение существует и не превышает 1000000.

Входные данные: в первой строке число N, не превышающее 10000, во второй число С, не превышающее 10, далее С строк, содержащих номера цветов (без пробелов), уместных после каждого цвета (3-я соответствует цвету 0, 4-я цвету 1 и т.п.).

Выходные данные: : в единственной строке единственное число – минимальная длина гирлянды.

Пример: Предположим, доступны 3 цвета: голубой (0) фиолетовый (1) и зелёный (2). После голубого всегда следует фиолетовый, после зелёного фиолетовый или голубой, после фиолетового - зелёный. А в деревне 10 жителей. Тогда входные данные будут выглядеть так:
10
3
1
2
10
При таких данных придётся делать гирлянды из 6 лампочек.