← 返回题目列表

Codeforces · 1431/H

H. Rogue-like 游戏

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

玛丽娜玩了一款新的 Rogue-like 游戏。在这个游戏中,有$$$n$$$不同的角色种类和$$$m$$$不同的类别。比赛以跑动方式进行;每次运行,玛丽娜都必须为她的角色选择一个物种和一个类别。如果她选择第 $$$i$$$ 个物种和第 $$$j$$$ 个类别,她将在这次运行中获得 $$$c_{i, j}$$$ 分数。

最初,一些物种和类别被解锁,所有其他物种和类别被锁定。要解锁第 $$$i$$$ 个物种,玛丽娜必须在之前的游戏中获得至少 $$$a_i$$$ 分 — 也就是说,一旦她的游戏总得分至少为 $$$a_i$$$,该物种就会解锁。同样,要解锁第 $$$j$$$ 类,她必须在之前的运行中总共获得至少 $$$b_j$$$ 点。如果对于某些 $$$i$$$,$$$a_i = 0$$$,则该物种最初会被解锁(这同样适用于 $$$b_j = 0$$$ 的类)。

玛丽娜希望以最少的运行次数解锁所有物种和类别。在玩游戏之前,她可以准确地阅读一份关于物种和类别的某种组合的指南,并且阅读指南将使她在该组合的所有运行中获得的分数增加$$$k$$$(正式地,在玩游戏之前,她可以将$$$c_{i, j}$$$的值增加$$$k$$$)。

如果她选择最佳组合来阅读指南,那么她必须玩多少次才能解锁所有物种和类别?

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 1500$$$; $$$0 \le k \le 10^9$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 = a_1 \le a_2 \le \dots \le a_n \le 10^{12}$$$),其中 $$$a_i$$$ 是解锁所需的点数$$$i$$$ 个物种(或 $$$0$$$,如果最初解锁)。请注意,$$$a_1 = 0$$$,并且这些值是非降序的。

第三行包含 $$$m$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$ ($$$0 = b_1 \le b_2 \le \dots \le b_m \le 10^{12}$$$),其中 $$$b_i$$$ 是解锁所需的点数$$$i$$$ 级(或 $$$0$$$,如果最初解锁)。请注意,$$$b_1 = 0$$$,并且这些值是非降序的。

接下来是 $$$n$$$ 行,每行包含 $$$m$$$ 个整数。第 $$$i$$$ 行中的第 $$$j$$$ 整数是 $$$c_{i, j}$$$ ($$$1 \le c_{i, j} \le 10^9$$$) — Marina 在第 $$$i$$$ 个物种和第 $$$j$$$ 个类别的运行中获得的分数。

输出

打印一个整数——如果玛丽娜在玩游戏之前能够准确阅读一本指南,那么她必须玩的最少运行次数才能解锁所有物种和所有类别。

示例

输入 #1

3 4 2
0 5 7
0 2 6 10
2 5 5 2
5 3 4 4
3 4 2 4

输出 #1

3

输入 #2

4 2 1
0 3 9 9
0 2
3 3
5 1
1 3
2 3

输出 #2

2

输入 #3

3 3 5
0 8 11
0 0 3
3 1 3
1 2 1
1 1 3

输出 #3

2

注意

第一次测试的说明:

1. Marina 阅读关于 $$$1$$$-st 物种和 $$$2$$$-nd 类组合的指南。因此,$$$c_{1, 2}$$$ 变为 $$$7$$$。最初,只有 $$$1$$$-st 物种和 $$$1$$$-st 等级被解锁。
2. Marina 与 $$$1$$$-st 物种和 $$$1$$$-st 类别进行跑步比赛。她的分数变为 $$$2$$$,并且她解锁了 $$$2$$$-nd 等级。
3. Marina 与 $$$1$$$-st 物种和 $$$2$$$-nd 类进行跑步比赛。她的分数变为 $$$9$$$,并且她解锁了除 $$$4$$$ 级之外的所有内容。
4. Marina 与 $$$3$$$-rd 物种和 $$$3$$$-rd 类别进行跑步比赛。她的分数变为 $$$11$$$,并且她解锁了 $$$4$$$ 级。她在 $$$3$$$ 运行中解锁了所有内容。

请注意,这种解锁所有内容的方法并不是唯一的方法。

第二次测试的说明:

1. Marina 阅读关于 $$$2$$$-nd 物种和 $$$1$$$-st 类组合的指南。因此,$$$c_{2, 1}$$$ 变为 $$$6$$$。最初,只有 $$$1$$$-st 物种和 $$$1$$$-st 等级被解锁。
2. Marina 与 $$$1$$$-st 物种和 $$$1$$$-st 类别进行跑步比赛。她的分数变为 $$$3$$$,并且她解锁了 $$$2$$$-nd 物种和 $$$2$$$-nd 类别。
3. Marina 与 $$$2$$$-nd 物种和 $$$1$$$-st 类进行跑步比赛。她的分数变为 $$$9$$$,并且她解锁了第 $$$3$$$ 个物种和第 $$$4$$$ 个物种。她在 $$$2$$$ 运行中解锁了所有内容。

与 $$$1$$$-st 示例一样,这并不是解锁 $$$2$$$ 运行中所有内容的唯一方法。