F. Cards and Joy
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.
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]\).
Print one integer — the maximum possible total joy levels of the players among all possible card distributions.
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\).