5. Shaman

Когда Миху выгнали из Политеха за неуспеваемость (Миха считал, что программистом можно стать и не зная математики, а Политех был другого мнения), он круто изменил жизненные планы и переквалифицировался из программиста в шамана. Шаман Ми-Ха изготавливал амулеты-чётки, предохраняющие от разнообразных несчастий.

Чётки собирались из бусин из разных пород деревьев (P пород, от липы до секвойи, причём все их Ми-Ха изготавливал из берёзовых дров на даче). При этом для убедительности Ми-Ха следовал им же обнародованным Правилам Следования: для бусины каждой породы было определено, бусины каких пород могут за ней следовать. Например, в чётках, предохраняющих от незачёта по программированию, за дубом мог следовать дуб или баобаб, за можжевельником - кедр, вяз или дуб...

В преддверии летней сессии Ми-Ха задумал выпустить партию из N эксклюзивных чёток для студентов. Все чётки должны быть разными, но соответствующими Правилам, и при этом одинаковой длины. Какой должна быть минимальная длина чёток? Гарантируется, что решение существует и не превышает 1000000.

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

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

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