463_D. Gargari and Permutations
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].
```python
n, k = 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)))
        

```