← 返回题目列表

AtCoder · asaporo_a

B. 魔术师高桥

中文机器翻译题面 查看原题

分数: 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