分数: 1200 点
问题陈述
高桥是一位魔术师。他可以对整数序列施咒 (a_1,a_2,...,a_M) 与 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) 这样 a_j = b_j (1 ≦ j < i) 和 a_i < b_i.
约束
- 1 ≦ N ≦ 10^3
- 1 ≦ M ≦ 10^3
- 让 j- 第一项 A_i be 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)}
输出
打印 Takahashi 需要执行的最少施法次数。如果他无法实现目标,请打印 -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