CF463D.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

加尔加里玩腻了主教相关的题目，现在在解决了那道题之后，他正尝试完成数学作业。在一本数学书中，他找到了 $k$ 个排列。每个排列均由数字 $1, 2, \dots, n$ 以某种顺序组成。现在他需要找出这 $k$ 个排列的最长公共子序列（LCS）的长度。你能帮帮他吗？

关于最长公共子序列，可参见：https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

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.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 1000$；$2 \leq k \leq 5$）。接下来的 $k$ 行每行包含 $1, 2, \dots, n$ 的一个排列——即当前排列的描述。

Print the length of the longest common subsequence.

输出最长公共子序列的长度。

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

第一个测试样例的答案是子序列 [1, 2, 3]。