Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.


-----Output-----

Print the length of the longest common subsequence.


-----Examples-----
Input
4 3
1 4 2 3
4 1 2 3
1 2 4 3

Output
3



-----Note-----

The answer for the first test sample is subsequence [1, 2, 3].

Difficulty: interview

Starter code:

Solutions:
def main():
    n, k = tuple(map(int, input().split()))

    a = [set(range(n)) for _ in range(n)]

    for i in range(k):
        p = set()
        for j in map(int, input().split()):
            a[j-1] -= p
            p.add(j-1)

    sa = sorted(list(range(n)), key=lambda i: len(a[i]))
    maxx = [0] * n
    res = 0
    
    for i in sa:
        m = 1 + maxx[max(a[i], key=lambda e: maxx[e])] if a[i] else 0
        maxx[i] = m
        res = max(res, m)

    print(res)


def __starting_point():
    main()


__starting_point()

n, k = list(map(int, input().split()))
ra = [[0] * k for _ in range(n)]
for p in range(k):
    for i, v in enumerate(map(int, input().split())):
        v -= 1
        ra[v][p] = i
g = [[] for _ in range(n)]
for u in range(n):
    for v in range(n):
        if all(x < y for x, y in zip(ra[u], ra[v])):
            g[u].append(v)

memo = [-1] * n
def dfs(v):
    if memo[v] != -1:
        return memo[v]
    r = 1
    for u in g[v]:
        r = max(r, dfs(u) + 1)
    memo[v] = r
    return r

print(max(dfs(s) for s in range(n)))
        


n, k = list(map(int, input().split()))
a, b = [[] for row in range(6)], [[0 for col in range(n + 1)] for row in range(6)]

for i in range(k):
    a[i] = list(map(int, input().split()))
    for j in range(n):
        b[i][a[i][j]] = j

dp = [1] * n
for i in range(n):
    for j in range(i):
        flag = 1
        for x in range(1, k):
            if b[x][a[0][j]] > b[x][a[0][i]]:
                flag = 0
                break
        if flag:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/14/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(N, K, A, pos):
    dp = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        maxx = 0
        for p in range(1, i):
            # if the A[1][p], A[1][i] is the last two elements of ans
            # A[1][p] should appears before A[1][i] at every input array A[1:]
            if all([pos[k][A[1][p]] < pos[k][A[1][i]] for k in range(2, K+1)]):
                maxx = max(maxx, dp[p])
        dp[i] = maxx + 1
    
    return max(dp)


N, K = map(int, input().split())
A = [[0] * (N + 1)]
pos = [[0 for _ in range(N+1)] for _ in range(K+1)]
for i in range(K):
    row = [0] + [int(x) for x in input().split()]
    A.append(row)
    for j, v in enumerate(row):
        pos[i+1][v] = j

print(solve(N, K, A, pos))

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/14/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


memo = [0 for _ in range(1005)]
def longestpath(start, graph):
    if memo[start] > 0:
        return memo[start]
    
    l = 0
    for v in graph[start]:
        l = max(longestpath(v, graph), l)
    memo[start] = l + 1
    return l + 1


def solve_graph(N, K, A, pos):
    # for each u, v if u appears before v in every array, add a link u->v
    g = collections.defaultdict(list)
    d = [0 for _ in range(N+1)]
    for u in range(1, N+1):
        for v in range(1, N+1):
            if all([pos[k][u] < pos[k][v] for k in range(1, K+1)]):
                g[u].append(v)
                d[v] += 1
    
    # then find the longest path
    ans = 0
    for u in range(1, N+1):
        if d[u] == 0:
            ans = max(ans, longestpath(u, g))
    return ans
    


def solve(N, K, A, pos):
    dp = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        maxx = 0
        for p in range(1, i):
            # if the A[1][p], A[1][i] is the last two elements of ans
            # A[1][p] should appears before A[1][i] at every input array A[1:]
            if all([pos[k][A[1][p]] < pos[k][A[1][i]] for k in range(2, K+1)]):
                maxx = max(maxx, dp[p])
        dp[i] = maxx + 1
    
    return max(dp)


N, K = map(int, input().split())
A = [[0] * (N + 1)]
pos = [[0 for _ in range(N+1)] for _ in range(K+1)]
for i in range(K):
    row = [0] + [int(x) for x in input().split()]
    A.append(row)
    for j, v in enumerate(row):
        pos[i+1][v] = j

print(solve_graph(N, K, A, pos))

#   ==========     //\\       //||     ||====//||
#       ||        //  \\        ||     ||   // ||
#       ||       //====\\       ||     ||  //  ||
#       ||      //      \\      ||     || //   ||
#   ========== //        \\  ========  ||//====|| 
#  code

def solve():
    n, k = map(int, input().split())
    c = [ [-1 for i in range(n + 1)] for i in range(k)]
    dp = [0 for i in range(n + 1)]
    a = []

    for i in range(k):
        b = list(map(int, input().split()))
        for j, v in enumerate(b):
            c[i][v] = j
        a.append(b)

    
    for i in range(n):
        curpos = a[0][i]
        dp[i] = 1
        for j in range(i):
            prevpos = a[0][j]
            ok = True
            for p in range(k):
                if c[p][curpos] < c[p][prevpos]:
                    ok = False
                    break
            if ok:
                dp[i] = max(dp[i], dp[j] + 1)
    print(max(dp))
    return

def main():
    t = 1
    # t = int(input())
    for _ in range(t):
        solve()

def __starting_point():
    main()
__starting_point()