Gargari 厌倦了和主教一起玩,现在,在解决了有关主教的问题后,他正在尝试做数学作业。在一本数学书中他找到了 k 个排列。它们每个都按某种顺序由数字 1、2、...、n 组成。现在他应该找到这些排列的最长公共子序列的长度。你能帮助加加里吗?
您可以在那里阅读最长公共子序列:https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5)。接下来的 k 行中的每一行都包含按某种顺序排列的整数 1, 2, ..., n — 当前排列的描述。
输出
打印最长公共子序列的长度。
示例
输入 #1
4 3 1 4 2 3 4 1 2 3 1 2 4 3
输出 #1
3
注意
第一个测试样本的答案是子序列 [1, 2, 3]。