← 返回题目列表

Codeforces · 463/D

D. Gargari 和排列

中文机器翻译题面 查看原题

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]。