30766번 - Клавиатура и вирус 다국어

문제

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

С помощью своей клавиатуры Коля печатает на $n$ различных языках. По счастливому стечению обстоятельств количество букв в каждом из этих языков совпадает с количеством клавиш на Колиной винтажной клавиатуре и равняется $m$. Все символы всех языков присутствуют в используемой Колей кодировке и, следовательно, могут быть представлены как числа от 1ドル$ до $c$. Один и тот же символ может присутствовать в произвольном количестве языков, но для двух различных языков обязательно найдётся хотя бы один символ, который есть в одном из них и отсутствует в другом. Некоторые числа от 1ドル$ до $c$ могут быть не заняты ни одним известным Коле символом.

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

• Вместо переключения на какой-то определённый язык, он меняется на совершенно случайно выбранный из $n$ языков, используемых Колей (при этом язык может и не измениться).
• Раскладка клавиатуры для данного языка перемешивается произвольным образом, выполняется лишь одно условие --- разным клавишам соответствуют разные символы.

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

입력

Первая строка входных данных содержит два числа $n$ и $m$ --- количество языков, используемых Колей, и количество клавиш на его новой клавиатуре (а заодно и букв во всех языках) соответственно.

Следующие $n$ строк описывают языки. Каждая из них содержит описание одного языка, состоящее из $m$ номеров символов в Колиной кодировке. Номера даны в произвольном порядке. Все номера --- целые числа от 1ドル$ до $c$. Параметр $c$ не даётся в тесте, но известен для каждой группы тестов.

Гарантируется, что $n,ドル $m$ и $c$ положительные.

출력

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

제한

노트

В первом тесте из условия, если Коле не повезёт и он нажмёт на клавиши, соответствующие 1ドル$ и 3ドル,ドル то он не сможет понять, на каком языке пишет.