310391: CF1826E. Walk the Runway

E. Walk the Runwaytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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}} < 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.

Input

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$.

Output

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

ExamplesInput

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

Output

30

Input

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

Output

50

Input

1 1
1000000000
1

Output

1000000000

Input

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

Output

5000000000

Input

1 3
1 2 3
3 3 3

Output

3

Note

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$.

题目大意：
题目是关于选择模特参加时装周巡回演出以获得最大利润的问题。有m个城市和n个模特，每个城市的观众对模特的评分不同。需要选择k个模特，并确定他们的出场顺序，使得在每个城市的表演中，模特的评分都是严格递增的。选择第j个模特参加巡回演出可以获得p_j的利润。目标是计算在满足所有要求的情况下，能获得的最大总利润。

输入数据格式：
第一行包含两个整数m和n，分别表示演出的城市数量和愿意参加的模特数量。
第二行包含n个整数p_j，表示邀请第j个模特参加演出的利润。
接下来的m行，每行包含n个整数，第i行表示第i个城市对每个模特的评分r_{i, j}。

输出数据格式：
输出一个整数，表示能获得的最大总利润。

请注意，以上内容是根据您提供的网页内容翻译的，具体问题可能需要根据上下文进一步理解。题目大意： 题目是关于选择模特参加时装周巡回演出以获得最大利润的问题。有m个城市和n个模特，每个城市的观众对模特的评分不同。需要选择k个模特，并确定他们的出场顺序，使得在每个城市的表演中，模特的评分都是严格递增的。选择第j个模特参加巡回演出可以获得p_j的利润。目标是计算在满足所有要求的情况下，能获得的最大总利润。 输入数据格式： 第一行包含两个整数m和n，分别表示演出的城市数量和愿意参加的模特数量。 第二行包含n个整数p_j，表示邀请第j个模特参加演出的利润。 接下来的m行，每行包含n个整数，第i行表示第i个城市对每个模特的评分r_{i, j}。 输出数据格式： 输出一个整数，表示能获得的最大总利润。 请注意，以上内容是根据您提供的网页内容翻译的，具体问题可能需要根据上下文进一步理解。