Дисертація Ібрагіма

Ібрагім закінчує навчання цього року і досліджує найдовшу спільну підпослідовність для невеликої частини своєї дисертації. У своєму дослідженні йому потрібно було знайти найдовшу спільну підпослідовність перестановок. Ібрагім не дуже вправний у перестановках. Допоможіть йому у цьому.

Вам задано кількість перестановок $k$. Кожна перестановка — це послідовність чисел $1,2,...,n$ у довільному порядку. Знайдіть довжину найбільшої спільної підпослідовності заданих перестановок.

Примітка 1. Послідовність чисел $1,2,...,n$, записана у довільному порядку, називається перестановкою з $n$ елементів.

Примітка 2. Підпослідовність послідовності — це послідовність, яку можна отримати з заданої послідовності, видаливши деякі елементи без зміни порядку інших елементів або не видаляючи жодного елемента. Підпослідовність, яка входить до двох або більше послідовностей, називається спільною підпослідовністю цих послідовностей.

Вхідні дані

У першому рядку задано два цілих числа $n(1\le n\le 1000)$ та $k(2\le k\le 5)$. У кожному з наступних $k$ рядків задана перестановка, що складається з $n$ цілих чисел $1,2,...,n$.

Вихідні дані

Виведіть довжину найбільшої спільної підпослідовності заданих перестановок.

Приклади

У першому прикладі послідовність $235$ або $245$ є найбільшою спільною підпослідовністю. Вони обидві зустрічаються у обох перестановках.

У другому прикладі $123$ — найбільша спільна підпослідовність. Вона зустрічається у всіх трьох перестановках.