Ібрагім закінчує навчання цього року і досліджує найдовшу спільну підпослідовність для невеликої частини своєї дисертації. У своєму дослідженні йому потрібно було знайти найдовшу спільну підпослідовність перестановок. Ібрагім не дуже вправний у перестановках. Допоможіть йому у цьому.
Вам задано кількість перестановок k. Кожна перестановка — це послідовність чисел 1,2,...,n у довільному порядку. Знайдіть довжину найбільшої спільної підпослідовності заданих перестановок.
Примітка 1. Послідовність чисел 1,2,...,n, записана у довільному порядку, називається перестановкою з n елементів.
Примітка 2. Підпослідовність послідовності — це послідовність, яку можна отримати з заданої послідовності, видаливши деякі елементи без зміни порядку інших елементів або не видаляючи жодного елемента. Підпослідовність, яка входить до двох або більше послідовностей, називається спільною підпослідовністю цих послідовностей.
У першому рядку задано два цілих числа n (1≤n≤1000) та k (2≤k≤5). У кожному з наступних k рядків задана перестановка, що складається з n цілих чисел 1,2,...,n.
Виведіть довжину найбільшої спільної підпослідовності заданих перестановок.
У першому прикладі послідовність 2 3 5 або 2 4 5 є найбільшою спільною підпослідовністю. Вони обидві зустрічаються у обох перестановках.
У другому прикладі 1 2 3 — найбільша спільна підпослідовність. Вона зустрічається у всіх трьох перестановках.