Cards and Joy

题目描述

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.

输入输出样例

输入样例 #1

4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7

输出样例 #1

21

输入样例 #2

3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3

输出样例 #2

0

说明

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