B - 魔法使い高橋君 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1200 点

問題文

高橋君は魔法使いです。高橋君は魔法をかけることで、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 が成り立つことを指します。

制約

  • 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 が成立する。

入力

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

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

Score : 1200 points

Problem Statement

Takahashi is a magician. He can cast a spell on an integer sequence (a_1,a_2,...,a_M) with M terms, to turn it into another sequence (s_1,s_2,...,s_M), where s_i is the sum of the first i terms in the original sequence.

One day, he received N integer sequences, each with M terms, and named those sequences A_1,A_2,...,A_N. He will try to cast the spell on those sequences so that A_1 < A_2 < ... < A_N will hold, where sequences are compared lexicographically. Let the action of casting the spell on a selected sequence be one cast of the spell. Find the minimum number of casts of the spell he needs to perform in order to achieve his objective.

Here, for two sequences a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M) with M terms each, a < b holds lexicographically if and only if there exists i (1 ≦ i ≦ M) such that a_j = b_j (1 ≦ j < i) and a_i < b_i.

Constraints

  • 1 ≦ N ≦ 10^3
  • 1 ≦ M ≦ 10^3
  • Let the j-th term in A_i be A_{(i,j)}, then 1 ≦ A_{(i,j)} ≦ 10^9.

Partial Scores

  • In the test set worth 200 points, Takahashi can achieve his objective by at most 10^4 casts of the spell, while keeping the values of all terms at most 10^9.
  • In the test set worth another 800 points, A_{(i,j)} ≦ 80.

Input

The input is given from Standard Input in the following format:

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)}

Output

Print the minimum number of casts of the spell Takahashi needs to perform. If he cannot achieve his objective, print -1 instead.

Sample Input 1

3 3
2 3 1
2 1 2
2 6 3

Sample Output 1

1

Takahashi can achieve his objective by casting the spell on A_2 once to turn it into (2 , 3 , 5).

Sample Input 2

3 3
3 2 10
10 5 4
9 1 9

Sample Output 2

-1

In this case, Takahashi cannot achieve his objective by casting the spell any number of times.

Sample Input 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

Sample Output 3

11