Problem Description

Takahashi is a magician. By casting a spell, he can transform a sequence of \( M \) terms \( (a_1, a_2, ..., a_M) \) into a sequence \( (s_1, s_2, ..., s_M) \) where \( s_i \) is the sum of \( a_1 \) to \( a_i \).

One day, Takahashi received \( N \) sequences of \( M \) terms each, which he named \( A_1, A_2, ..., A_N \). He wants to cast spells to make them lexicographically sorted in the order \( A_1 < A_2 < ... < A_N \). Takahashi considers casting a spell on one sequence as one spell. Determine the minimum number of spells Takahashi needs to achieve his goal.

Two sequences \( a = (a_1, a_2, ..., a_M) \) and \( b = (b_1, b_2, ..., b_M) \) are lexicographically ordered as \( a < b \) if there exists an \( i \) ( \( 1 \leq i \leq M \) ) such that \( a_j = b_j \) for \( 1 \leq j < i \) and \( a_i < b_i \).

Input Format

The input is given from the 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 Format

Output the minimum number of spells Takahashi needs to cast. If it is impossible for Takahashi to achieve his goal, output -1 instead.

Sample Input and Output

Sample Input #1

3 3
2 3 1
2 1 2
2 6 3

Sample Output #1

1

Sample Input #2

3 3
3 2 10
10 5 4
9 1 9

Sample Output #2

-1

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

Notes/Hints

Constraints

• \( 1 \leq N \leq 10^3 \)
• \( 1 \leq M \leq 10^3 \)
• \( 1 \leq A_{(i,j)} \leq 10^9 \)

Partial Points

• For 200 points of test cases, it is possible to achieve the goal with at most \( 10^4 \) spells, and all terms are \( 10^9 \) or less.
• For another 800 points of test cases, \( A_{(i,j)} \leq 80 \) holds.

Sample Explanation 1

By casting one spell on \( A_2 \), it becomes \( (2, 3, 5) \), and Takahashi can achieve his goal.

Sample Explanation 2

In this case, no matter how many spells Takahashi casts, he cannot achieve his goal.

见题面 Input 部分

见题面 Output 部分