← 返回题目列表

Codeforces · 1936/C

C. 神奇宝贝竞技场

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

你在决斗场。您还拥有 $$$n$$$ 神奇宝贝。最初,只有 $$$1$$$-st 神奇宝贝站在竞技场中。

每个神奇宝贝都有 $$$m$$$ 属性。第 $$$i$$$ 个神奇宝贝的第 $$$j$$$ 属性是 $$$a_{i,j}$$$。每个神奇宝贝还有一个雇佣成本:第 $$$i$$$ 个神奇宝贝的成本是 $$$c_i$$$。

您想让第 $$$n$$$ 个神奇宝贝站在竞技场中。为此,您可以按任意顺序执行任意次数的以下两种类型的操作:

- 选择三个整数 $$$i$$$、$$$j$$$、$$$k$$$ ($$$1 \le i \le n$$$、$$$1 \le j \le m$$$、$$$k > 0$$$),将 $$$a_{i,j}$$$ 永久增加 $$$k$$$。此操作的成本为 $$$k$$$。
- 选择两个整数 $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) 并根据第 $$$j$$$ 属性雇用第 $$$i$$$ 个神奇宝贝与竞技场中当前的神奇宝贝决斗。如果$$$a_{i,j}$$$大于或等于竞技场中当前神奇宝贝的第$$$j$$$属性,则第$$$i$$$个神奇宝贝将获胜(否则将失败)。决斗结束后,只有获胜者才能站在竞技场上。此操作的成本为$$$c_i$$$。

求出让第 $$$n$$$ 个神奇宝贝站在竞技场中所需支付的最低成本。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 4 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$2 \leq n \cdot m \leq 4 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$)。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^9$$$)。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,输出使第 $$$n$$$ 个神奇宝贝站在竞技场中的最小成本。

示例

输入 #1

4
3 3
2 3 1
2 9 9
6 1 7
1 2 1
3 3
2 3 1
9 9 9
6 1 7
1 2 1
4 2
2 8 3 5
18 24
17 10
1 10
1 1
6 3
21412674 3212925 172015806 250849370 306960171 333018900
950000001 950000001 950000001
821757276 783362401 760000001
570000001 700246226 600757652
380000001 423513575 474035234
315201473 300580025 287023445
1 1 1

输出 #1

2
6
17
1224474550

注意

在第一个测试用例中,$$$1$$$-st神奇宝贝(最初站在竞技场中)的属性数组是$$$[2,9,9]$$$。

在第一个操作中,您可以选择$$$i=3$$$、$$$j=1$$$、$$$k=1$$$,并将$$$a_{3,1}$$$永久增加$$$1$$$。现在$$$3$$$-rd神奇宝贝的属性数组是$$$[2,2,1]$$$。此操作的成本为 $$$k = 1$$$。

在第二个操作中,您可以选择$$$i=3$$$、$$$j=1$$$,并根据$$$1$$$-st属性雇佣$$$3$$$-rd神奇宝贝与竞技场中当前的神奇宝贝进行决斗。由于 $$$a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}$$$,$$$3$$$-rd 神奇宝贝将获胜。此操作的成本为 $$$c_3 = 1$$$。

因此,我们以$$$2$$$的成本让第$$$3$$$个神奇宝贝站在竞技场中。可以证明 $$$2$$$ 是最小可能的。

在第二个测试用例中,竞技场中$$$1$$$-st神奇宝贝的属性数组是$$$[9,9,9]$$$。

在第一次操作中,您可以选择$$$i=2$$$、$$$j=3$$$、$$$k=2$$$,并将$$$a_{2,3}$$$永久增加$$$2$$$。现在第$$$2$$$个神奇宝贝的属性数组是$$$[6,1,9]$$$。此操作的成本为 $$$k = 2$$$。

在第二个操作中,你可以选择$$$i=2$$$、$$$j=3$$$,并根据$$$3$$$-rd属性雇佣$$$2$$$-nd神奇宝贝与竞技场中当前的神奇宝贝进行决斗。由于 $$$a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}$$$,第 $$$2$$$ 个神奇宝贝将获胜。此操作的成本为 $$$c_2 = 3$$$。

在第三个操作中,你可以选择$$$i=3$$$、$$$j=2$$$,根据$$$2$$$-nd属性雇佣$$$3$$$-rd神奇宝贝与竞技场中当前的神奇宝贝进行决斗。由于 $$$a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}$$$,$$$3$$$-rd 神奇宝贝可以获胜。此操作的成本为 $$$c_3 = 1$$$。

因此,我们以$$$6$$$的成本让第$$$3$$$个神奇宝贝站在竞技场中。可以证明 $$$6$$$ 是最小可能的。