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

• 每个位置i有k个候选值，记为1≤ai,1≤⋯≤ai,k；
• 需从每个位置的候选值中选取恰好一个数构成序列$a$。

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

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

接下来$n$行，每行$k$个数，即 ai,1,ai,2,⋯,ai,k。

样例 1 说明

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

• 
  数据点$1：$$k=1，$$n\le 10^3$。
  


• 
  数据点$2\sim 3：$$n,k\le 100$。
  


• 
  数据点$4\sim 6$：$k\le 10^3$。
  


• 
  数据点$7\sim 10$：无特殊限制。
  

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

梦熊第一套练习题，动态规划