A fashion tour consists of m� identical runway shows in different cities. There are n� models willing to participate in the tour, numbered from 11 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 ri,j��,�.
You are to choose some number of k� models, and their order, let the chosen models have indices j1,j2,…,jk�1,�2,…,�� 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≤t≤k2≤�≤�), the ratings must satisfy ri,jt−1<ri,jt��,��−1<��,��.
After all, the fashion industry is all about money, so choosing model j� to participate in the tour profits you pj�� money. Compute the maximum total profit you can make by choosing the models and their order while satisfying all the requirements.
Walk the Runway Solution Codeforces
The first line contains two integers m� and n� (1≤m≤5001≤�≤500, 1≤n≤50001≤�≤5000) — the number of shows and the number of models willing to participate respectively.
The second line contains n� integers pj�� (1≤pj≤1091≤��≤109) — 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 ri,j��,� (1≤ri,j≤n1≤��,�≤�) — the ratings of models in city i�.
Walk the Runway Solution Codeforces
Output a single integer — the largest total amount of money you can get.
Examples
3 5 10 10 10 10 10 1 2 3 4 5 1 5 2 3 4 2 3 4 5 1
3 5 10 10 10 10 50 1 2 3 4 5 1 5 2 3 4 2 3 4 5 1
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
Walk the Runway Solution Codeforces
In the first example, there are 33 invited models. The show consists of models in the order [1,3,4][1,3,4].
Then, the corresponding ratings in the cities are as follows:
- City 11 — [1,3,4][1,3,4].
- City 22 — [1,2,3][1,2,3].
- City 33 — [2,4,5][2,4,5].
You can see that the ratings are increasing. So the total profit is 10+10+10=3010+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 5050. 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 10000000001000000000.
In the fourth test case, we can invite all the models and make the show in the order [5,4,3,2,1][5,4,3,2,1]. The total profit is 5⋅1000000000=50000000005⋅1000000000=5000000000.