AT_asaporo_a 魔法使い高橋君
题目描述
高桥君是一个魔法师。他可以通过施魔法来将一个由M个元素组成的数列(A1, A2, ..., AM)转换为其前缀和序列(S1, S2, ..., SM)。
一天，高桥君收到了N个数列，并将它们命名为A1, A2, ..., AN，他想通过施魔法使得这些数列按字典序递增排序。高桥君可以选择一个数列并施魔法一次。请问，使得所有数列按照字典序递增排序的最小魔法施放次数是多少？
其中，对于两个由M个元素组成的数列a=(a1,a2,...,aM)和b=(b1,b2,...,bM)，若它们在字典序中满足a
输入格式
从标准输入中读入如下格式的输入：
N M
(1,1) A(1,1) (1,2) A(1,2) ... (1,M) A(1,M)
(2,1) A(2,1) (2,2) A(2,2) ... (2,M) A(2,M)
...
(N,1) A(N,1) (N,2) A(N,2) ... (N,M) A(N,M)
输出格式
将高桥君施放魔法的最小次数输出。若无法使得数列按照字典序递增排序，则输出-1。
## 输入输出样例
输入 #1
3 3
2 3 1
2 1 2
2 6 3
输出 #1
1
输入 #2
3 3
3 2 10
10 5 4
9 1 9
输出 #2
-1
输入 #3
5 5
2 6 5 6 9
2 6 4 9 10
2 6 8 6 7
2 1 7 3 8
2 1 4 8 3
输出 #3
11
说明/提示
$1 \leq N \leq 10$
$1 \leq M \leq 10$
$1 \leq A_{i,j} \leq 10^9$
部分分：
200分的测试用例中，可以用不超过4次魔法，将序列中每项不超过$10^9$，的序列变为字典序递增。
对于另外800分的测试用例，有$1 \leq A_{i,j} \leq 80$。
样例解释：
样例1中，对于$A_2$，只需要使用1次魔法，将其变为$(2,3,5)$即可达成目标。
样例2中，无论使用多少次魔法，都无法将序列变为字典序递增，因此输出-1。