Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

D. Gargari и перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Gargari надоело играть со слонами на шахматной доске из предыдущей задачи, теперь он собирается сделать домашнюю работу по математике. В его учебнике по математике записаны k перестановок. Каждая перестановка — это последовательность чисел 1, 2, ..., n, записанных в некотором порядке. Gargari должен найти длину наибольшей общей подпоследовательности этих k перестановок. Сможете ли вы ему помочь?

Определение задачи о наибольшей общей подпоследовательности можно найти по ссылке: https://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность

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

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). В каждой из следующих k строк записаны целые числа 1, 2, ..., n в некотором порядке — описание текущей перестановки.

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

Выведите длину наибольшей общей подпоследовательности.

Примеры
Входные данные
4 3
1 4 2 3
4 1 2 3
1 2 4 3
Выходные данные
3
Примечание

В первом тестовом примере наибольшая общая подпоследовательность: [1, 2, 3].