Cards and Joy
Contest: Codeforces Round 490 (Div. 3)
Difficulty rating: 2000
Tags: dp

There are $$$n$$$ players sitting at the card table. Each player has a favorite number. The favorite number of the $$$j$$$-th player is $$$f_j$$$.

There are $$$k \cdot n$$$ cards on the table. Each card contains a single integer: the $$$i$$$-th card contains number $$$c_i$$$. Also, you are given a sequence $$$h_1, h_2, \dots, h_k$$$. Its meaning will be explained below.

The players have to distribute all the cards in such a way that each of them will hold exactly $$$k$$$ cards. After all the cards are distributed, each player counts the number of cards he has that contains his favorite number. The joy level of a player equals $$$h_t$$$ if the player holds $$$t$$$ cards containing his favorite number. If a player gets no cards with his favorite number (i.e., $$$t=0$$$), his joy level is $$$0$$$.

Print the maximum possible total joy levels of the players after the cards are distributed. Note that the sequence $$$h_1, \dots, h_k$$$ is the same for all the players.

Input format:
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 500, 1 \le k \le 10$$$) — the number of players and the number of cards each player will get.

The second line contains $$$k \cdot n$$$ integers $$$c_1, c_2, \dots, c_{k \cdot n}$$$ ($$$1 \le c_i \le 10^5$$$) — the numbers written on the cards.

The third line contains $$$n$$$ integers $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_j \le 10^5$$$) — the favorite numbers of the players.

The fourth line contains $$$k$$$ integers $$$h_1, h_2, \dots, h_k$$$ ($$$1 \le h_t \le 10^5$$$), where $$$h_t$$$ is the joy level of a player if he gets exactly $$$t$$$ cards with his favorite number written on them. It is guaranteed that the condition $$$h_{t - 1} < h_t$$$ holds for each $$$t \in [2..k]$$$.

Output format:
Print one integer — the maximum possible total joy levels of the players among all possible card distributions.

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

Note:
In the first example, one possible optimal card distribution is the following:

- Player $$$1$$$ gets cards with numbers $$$[1, 3, 8]$$$;
- Player $$$2$$$ gets cards with numbers $$$[2, 2, 8]$$$;
- Player $$$3$$$ gets cards with numbers $$$[2, 2, 8]$$$;
- Player $$$4$$$ gets cards with numbers $$$[5, 5, 5]$$$.

Thus, the answer is $$$2 + 6 + 6 + 7 = 21$$$.

In the second example, no player can get a card with his favorite number. Thus, the answer is $$$0$$$.

Example input:
4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7

Example output:
21

Example input:
3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3

Example output:
0

Editorial:
It is obvious that we can solve the problem separately for each favorite number because each player has only one favorite number, and if the player gets a card not having his favorite number, his joy will not change.
Let $$$\mathit{dp}[x][y]$$$ be the maximum possible total joy of $$$x$$$ players with the same favorite number (it doesn't matter which one) and $$$y$$$ cards (containing their favorite number) if the cards are distributed among the players optimally. Note that $$$x \in [0, n]$$$ and $$$y \in [0, k \cdot n]$$$. At the beginning, all entries of the $$$\mathit{dp}$$$ table are zeroes. The transition in this dynamic programming depends on how many cards the $$$x$$$-th player will receive (which is between $$$0$$$ and $$$k$$$). In other words, the dynamic programming transition will look like:
where $$$h[i]$$$ is the joy of the player if he receives exactly $$$i$$$ cards containing his favorite number. Note that $$$h[0] = 0$$$.
After filling the $$$\mathit{dp}$$$ table, the answer can be calculated very easily: $$$\mathit{ans} = \sum\limits_{i = 1}^{10^5}\mathit{dp}[f_i][c_i]$$$, where $$$f_i$$$ is the number of players with favorite number $$$i$$$ and $$$c_i$$$ is the number of cards containing the number $$$i$$$.
Time complexity is $$$O(n^2 \cdot k^2)$$$.