一场时尚之旅由不同城市的 $$$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$$$。