Walk the Runway
Contest: Codeforces Round 870 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, data structures, dp, graphs, implementation, sortings

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 format:
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 format:
Output a single integer — the largest total amount of money you can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3 5
10 10 10 10 10
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1

Example output:
30

Example input:
3 5
10 10 10 10 50
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1

Example output:
50

Editorial:
At first, let's define the relation between two models, that go one after another in the show. Their ratings must satisfy $$$r_{i, j} < r_{i, k}$$$ for all cities $$$i$$$. Now let's precompute this relations for all pairs of models naively in $$$O(n^2m)$$$, which is ok for now.
Now, we have the relations "model $$$i$$$ can go before model $$$j$$$", let's build a graph of such relations. This graph has no cycles, since the ratings are strictly increasing. Now we can build the topological sorting of this graph and compute $$$dp_i = $$$ the biggest profit, if the last model is model $$$i$$$ in $$$O(n^2)$$$.
Now, how to calculate this relation for all pairs of models fast enough? Let's process each city one by one and update the relations using bitsets! More formally, let's store a bitset of all the models, that can be before model $$$j$$$ in city $$$i$$$. If we process the models in order of increasing rating, we can update each models bitset of relations in $$$O(\frac{n}{64})$$$, so the total time complexity would be $$$O(\frac{n^2m}{64})$$$, which is fast enough.