CF1826E.Walk the Runway

A fashion tour consists of $m$ identical runway shows in different cities. There are $n$ models willing to participate in the tour, numbered from $1$ to $n$. People in different cities have different views on the fashion industry, so they rate each model differently. In particular, people in city $i$ rate model $j$ with rating $r_{i, j}$.

You are to choose some number of $k$ models, and their order, let the chosen models have indices $j_1, j_2, \dots, j_k$ in the chosen order. In each city, these $k$ models will walk the runway one after another in this order. To make the show exciting, in each city, the ratings of models should be strictly increasing in the order of their performance. More formally, for any city $i$ and index $t$ ($2 \leq t \leq k$), the ratings must satisfy $r_{i,j_{t - 1}} \lt r_{i,j_t}$.

After all, the fashion industry is all about money, so choosing model $j$ to participate in the tour profits you $p_j$ money. Compute the maximum total profit you can make by choosing the models and their order while satisfying all the requirements.

一场时装巡演包含在 $m$ 个不同城市举行的 $m$ 场完全相同的时装秀。共有 $n$ 位模特愿意参加此次巡演，编号为 $1$ 至 $n$。不同城市的观众对时尚产业的看法各异，因此他们对每位模特的评分也不同。具体而言，第 $i$ 个城市对第 $j$ 位模特的评分为 $r_{i, j}$。

你需要从中选出 $k$ 位模特（$k$ 可为任意非负整数），并确定其出场顺序；设所选模特按出场顺序的编号依次为 $j_1, j_2, \dots, j_k$。在每个城市中，这 $k$ 位模特将严格按此顺序依次走上T台。为使时装秀富有观赏性，要求在每个城市中，模特们的评分必须严格递增。更准确地说，对任意城市 $i$ 和任意索引 $t$（其中 $2 \leq t \leq k$），评分需满足 $r_{i,j_{t - 1}} \lt r_{i,j_t}$。

最终，时尚产业归根结底关乎收益：选择第 $j$ 位模特参与巡演可为你带来 $p_j$ 的利润。请计算在满足上述所有约束条件下，你能获得的最大总利润。

The first line contains two integers $m$ and $n$ ($1 \leq m \leq 500$, $1 \leq n \leq 5000$) — the number of shows and the number of models willing to participate respectively.

The second line contains $n$ integers $p_j$ ($1 \leq p_j \leq 10^9$) — the profit you get inviting the $j$-th model to the tour.

The next $m$ lines each contain $n$ integers. Line number $i$ contains $n$ integers $r_{i, j}$ ($1 \leq r_{i, j} \leq n$) — the ratings of models in city $i$.

第一行包含两个整数 $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$）—— 表示第 $j$ 位模特在第 $i$ 座城市的评分。

Output a single integer — the largest total amount of money you can get.

输出一个整数——你能获得的最大总金额。

In the first example, there are $3$ invited models. The show consists of models in the order $[1, 3, 4]$.

Then, the corresponding ratings in the cities are as follows:

• City $1$ — $[ 1, 3, 4 ]$.
• City $2$ — $[ 1, 2, 3 ]$.
• City $3$ — $[ 2, 4, 5 ]$.

You can see that the ratings are increasing. So the total profit is $10 + 10 + 10 = 30$. It can be proven that we can't achieve a bigger profit.

In the second example, we can invite the fifth model to the tour, which would result in a total profit of $50$. It can be proven that we can't achieve a bigger profit.

In the third example, we invite the single model to the tour, which results in a total profit of $1\,000\,000\,000$.

In the fourth test case, we can invite all the models and make the show in the order $[ 5, 4, 3, 2, 1 ]$. The total profit is $5 \cdot 1\,000\,000\,000 = 5\,000\,000\,000$.

在第一个例子中，共有 $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$。