AT_asaporo_a 魔法使い高橋君

高桥君是一个魔法师。他可以通过施魔法来将一个由 $M$ 个元素组成的数列 $(A_1,A_2,\dots,A_M)$ 转换为其前缀和序列 $(S_1,S_2,\dots,S_M)$。 一天，高桥君收到了 $N$ 个数列，并将它们命名为 $A_1,A_2,\dots,A_N$，他想通过施魔法使得这些数列按字典序递增排序。高桥君可以选择一个数列并施魔法一次。请问，使得所有数列按照字典序递增排序的最小魔法施放次数是多少？ 其中，对于两个由 $M$ 个元素组成的数列 $a=(a_1,a_2,\dots,a_M)$ 和 $b=(b_1,b_2,\dots,b_M)$，若它们在字典序中满足 $a

从标准输入中读入如下格式的输入： >$N$ $M\\$ >$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}\\$ >$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}\\$ >$\vdots\\$ >$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

将高桥君施放魔法的最小次数输出。若无法使得数列按照字典序递增排序，则输出 $-1$。

### 样例解释： 样例 $1$ 中，对于 $A_2$，只需要使用 $1$ 次魔法，将其变为 $(2,3,5)$ 即可达成目标。 样例 $2$ 中，无论使用多少次魔法，都无法将序列变为字典序递增，因此输出 $-1$。 ### 数据范围 对于 $100\%$ 的数据，满足： - $1 \leq N \leq 10$ - $1 \leq M \leq 10$ - $1 \leq A_{i,j} \leq 10^9$ 对于 $\frac{1}{6}$ 的测试用例，可以用不超过 $4$ 次魔法，将序列中每项不超过 $10^9$ 的序列变为字典序递增。 对于另外 $\frac{2}{3}$ 的测试用例，有 $1 \leq A_{i,j} \leq 80$。