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