题目描述

高桥君是一个魔法师。他可以通过施魔法来将一个由M个元素组成的数列(A1, A2, ..., AM)转换为其前缀和序列(S1, S2, ..., SM)。

一天，高桥君收到了N个数列，并将它们命名为A1, A2, ..., AN，他想通过施魔法使得这些数列按字典序递增排序。高桥君可以选择一个数列并施魔法一次。请问，使得所有数列按照字典序递增排序的最小魔法施放次数是多少？

其中，对于两个由M个元素组成的数列a=(a1,a2,...,aM)和b=(b1,b2,...,bM)，若它们在字典序中满足a<b，则有：存在一个1≤i≤M，使得a1=b1,a2=b2,...,ai−1=bi−1且ai<bi成 立。

输入格式：

从标准输入中读入如下格式的输入：

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。