配点 : $1200$ 点

問題文

高橋君は魔法使いです。高橋君は魔法をかけることで、$M$ 項からなる数列 $(a_1,a_2,...,a_M)$ を、$s_i$ を $a_1 \sim 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 \leq i \leq M)$ で $a_j = b_j (1 \leq j < i)$ かつ $a_i < b_i$ が成り立つことを指します。

制約

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

部分点

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

入力

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

$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 を出力せよ。

入力例1

3 3
2 3 1
2 1 2
2 6 3

出力例1

1

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

入力例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