← 返回题目列表

Codeforces · 1826/E

E. 走在跑道上

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

一场时尚之旅由不同城市的 $$$m$$$ 相同的时装秀组成。有$$$n$$$模特愿意参加巡演,编号从$$$1$$$到$$$n$$$。不同城市的人们对时尚行业的看法不同,因此对每个模特的评价也不同。特别是,城市 $$$i$$$ 对模型 $$$j$$$ 进行评分,评分为 $$$r_{i, j}$$$。

您需要选择一些数量的 $$$k$$$ 模型及其顺序,让所选模型的索引为 $$$j_1, j_2, \dots, j_k$$$ 按所选顺序。在每个城市,这些$$$k$$$的模特将按照这个顺序依次走上T台。为了让节目精彩,在每个城市,模特的评分严格按照表演顺序递增。更正式地说,对于任何城市 $$$i$$$ 和索引 $$$t$$$ ($$$2 \leq t \leq k$$$),评级必须满足 $$$r_{i,j_{t - 1}} < r_{i,j_t}$$$。

毕竟时尚界就是为了钱,所以选择模特$$$j$$$参加巡演可以赚到$$$p_j$$$钱。计算在满足所有要求的情况下,通过选择型号及其顺序可以赚取的最大总利润。

输入

第一行包含两个整数 $$$m$$$ 和 $$$n$$$ ($$$1 \leq m \leq 500$$$, $$$1 \leq n \leq 5000$$$) — 分别是演出数量和愿意参加的模特数量。

第二行包含 $$$n$$$ 整数 $$$p_j$$$ ($$$1 \leq p_j \leq 10^9$$$) — 您邀请第 $$$j$$$ 个模特参加巡演所获得的利润。

接下来的 $$$m$$$ 行每行包含 $$$n$$$ 个整数。行号 $$$i$$$ 包含 $$$n$$$ 整数 $$$r_{i, j}$$$ ($$$1 \leq r_{i, j} \leq n$$$) — 城市 $$$i$$$ 中模特的评分。

输出

输出一个整数——您可以获得的最大总金额。

示例

输入 #1

3 5
10 10 10 10 10
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1

输出 #1

30

输入 #2

3 5
10 10 10 10 50
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1

输出 #2

50

输入 #3

1 1
1000000000
1

输出 #3

1000000000

输入#4

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1

输出#4

5000000000

输入 #5

1 3
1 2 3
3 3 3

输出 #5

3

注意

在第一个示例中,有 $$$3$$$ 受邀模特。该节目由模特组成,顺序为 $$$[1, 3, 4]$$$。

那么各城市对应的评分如下:

- 城市 $$$1$$$ — $$$[ 1, 3, 4 ]$$$。
- 城市 $$$2$$$ — $$$[ 1, 2, 3 ]$$$。
- 城市 $$$3$$$ — $$$[ 2, 4, 5 ]$$$。

可以看到收视率正在上升。因此总利润为 $$$10 + 10 + 10 = 30$$$。事实证明,我们无法获得更大的利润。

在第二个示例中,我们可以邀请第五位模特参加巡演,这将导致总利润 $$$50$$$。事实证明,我们无法获得更大的利润。

在第三个例子中,我们邀请单一模特参加旅游,总利润为$$$1\,000\,000\,000$$$。

在第四个测试用例中,我们可以邀请所有模特并按照$$$[ 5, 4, 3, 2, 1 ]$$$的顺序进行表演。总利润为 $$$5 \cdot 1\,000\,000\,000 = 5\,000\,000\,000$$$。