题目描述

高橋君は魔法使いです。高橋君は魔法をかけることで、$M$ 項からなる数列 $(a_1,a_2,...,a_M)$ を、$s_i$ を $a_1～a_i$ の和とした数列 $(s_1,s_2,...,s_M)$ に変えることができます。

ある日、高橋君は $M$ 項からなる数列を $N$ 個もらい、順番に $A_1,A_2,...,A_N$ と名付けました。さらに、高橋君は魔法をかけることで、辞書順で比較した際に $A_1\ <\ A_2\ <\ ...\ <\ A_N$ となるようにしようと思いました。 高橋君が一つの数列を選んでそれに魔法をかける操作を $1$ 回の魔法とします。このとき、高橋君が目標を達成するために必要な魔法の最小回数を求めてください。

ただし、$M$ 項からなる $2$ つの数列 $ a\ =\ (a_1,a_2,...,a_M)\ ,\ b\ =\ (b_1,b_2,...,b_M) $ が辞書順で $a\ <\ b$ であるとは、ある $i\ (1\ ≦\ i\ ≦\ M)$ で $a_j\ =\ b_j\ (1\ ≦\ j\ <\ i)$ かつ $a_i\ <\ b_i$ が成り立つことを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_{(1,1)}$ $A_{(1,2)}$ $...$ $A_{(1,M)}$ $A_{(2,1)}$ $A_{(2,2)}$ $...$ $A_{(2,M)}$ $:$ $A_{(N,1)}$ $A_{(N,2)}$ $...$ $A_{(N,M)}$

输出格式

高橋君がかける魔法の最小回数を出力せよ。ただし、高橋君が目標を達成できないならば、代わりに -1 を出力せよ。

题目大意

题目描述

高桥君是一个魔法师。他可以通过施魔法来将一个由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。

3 3
2 3 1
2 1 2
2 6 3

1

3 3
3 2 10
10 5 4
9 1 9

-1

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

11

提示

制約

• $1\ ≦\ N\ ≦\ 10^3$
• $1\ ≦\ M\ ≦\ 10^3$
• $A_i$ の $j$ 項目を $A_{(i,j)}$ としたとき、 $1\ ≦\ A_{(i,j)}\ ≦\ 10^9$

部分点

• $200$ 点分のテストケースでは、$10^4$ 回以下の回数で目標を達成し、かつ、どの項も $10^9$ 以下となるようにすることができる。
• 別の $800$ 点分のテストケースでは、$A_{(i,j)}\ ≦\ 80$ が成立する。

Sample Explanation 1

$A_2$ に対して $1$ 回魔法をかけることで、$A_2\ =\ (2\ ,\ 3\ ,\ 5)$ となり、高橋君は目標を達成できます。

Sample Explanation 2

この場合、何回魔法をかけても高橋君は目標を達成できません。