题目描述

高桥是一名魔术师。他可以对一个整数序列 $(a_1,a_2,...,a_M)$ 进行咒语，将其变换为另一个序列 $(s_1,s_2,...,s_M)$，其中 $s_i$ 是原始序列前 $i$ 个项的和。

一天，他收到了 $N$ 个整数序列，每个序列有 $M$ 个项，并将这些序列命名为 $A_1,A_2,...,A_N$。他将尝试施加咒语，使得 $A_1 < A_2 < ... < A_N$ 成立，其中序列按字典顺序比较。假设施放咒语在一个选择的序列上的动作是一次咒语。找出他为了实现目标所需进行的最少咒语次数。

这里，对于两个序列 $a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M)$，如果每个序列都有 $M$ 个项，那么 $a < b$ 成立当且仅当存在 $i (1 ≤ i ≤ M)$ 使得对于所有 $j (1 ≤ j < i)$ 都有 $a_j = b_j$，且 $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$ 上，将其变为 $(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