来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 01 套，第 3 题。原题标号：C；原本地编号：Z4P1-01-C。

C. yet LIS

给定长度为 $n$ 的序列构造规则：

• 每个位置 $i$ 有 $k$ 个候选值，记为 $a_{ i,1}\le a_{i,2}\le\cdots\le a_{i,k}$；
• 需从每个位置的候选值中选取恰好一个数构成序列 $a$。

求所有可能序列的最长严格上升子序列（LIS）的最大长度。

输入格式

第一行两个数 $k, n$，意义如题述。

接下来 $n$ 行，每行 $k$ 个数，即 $a_{ i,1}, a_{i,2},\cdots, a_{i,k}$。

输出格式

仅一行一个整数，即所有可能的序列中的最长上升子序列的的最大长度。

样例

输入样例 1

2 2
1 3
1 2

输出样例 1

2

样例 1 说明

序列可能为 $\{1, 2\}$，这时最长上升子序列的长度为 $2$，是最长的长度。

样例 2

见选手目录下的 $\textit{\textbf{lis/lis2.in}}$ 与 $\textit{\textbf{lis/lis2.ans}}$。

该样例与测试数据 $4\sim 6$ 满足同样的约束条件。

数据规模与约定

• 数据点 $1$：$k=1$，$n\le 10^3$。
• 数据点 $2\sim3$：$n,k\le 100$。
• 数据点 $4\sim6$：$k\le 10^3$。
• 数据点 $7\sim10$：无特殊限制。

对于 $100\%$ 的数据，有 $1\le k\le 5 \times 10^3$，$1 \le n \le 10^3$，每个取值都是非负数，不超过 $10^3$。