| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 29 | 13 | 9 | 47.368% |
Dota 2 is a competitive multiplayer computer game. In this game, two teams of $n$ players are fighting each other in order to destroy the enemy main building, Ancient. Each player controls one hero, and each hero has exactly $s$ standard abilities and exactly one ultimate ability.
Ability Draft is a fun mode of Dota 2. In this mode, at the start of the game each player gets random hero without abilities at all. Then players pick abilities in certain order from the pool of abilities provided by the game. At his turn, player may either pick any of the remaining standard abilities, or, if he didn't pick his ultimate ability, pick any of the remaining ultimate abilities. The pool contains enough abilities of both kinds so that each player can always pick his $s$ standard abilities and one ultimate ability.
The strength of the team is the sum of strengths of all abilities of all heroes in this team. All players are picking abilities in such a way that the difference between the strength of their own team and the strength of the enemy team at the end of draft procedure is maximum possible.
Knowing the strengths of abilities in the pool and the order of ability picks, find the difference of strengths of the teams if all players perform their picks optimally.
The first line of input contains two integers $n$ and $s$ (1ドル \le n \le 5,ドル 1ドル \le s \le 3$) --- the number of players in the team and the number of standard abilities of the heroes.
The second line contains 2ドルn \cdot (s + 1)$ indices of players --- the order of ability picks. Each index from 1ドル$ to 2ドルn$ appears exactly $s + 1$ times in this array. Players with indices between 1 and $n$ belong to the first team, and players with indices between $n + 1$ and 2ドルn$ belong to the second team.
The third line contains an integer $p_s$ (2ドルn \cdot s \le p_s \le 36$) --- the number of standard abilities in the pool.
The fourth line contains $p_s$ integers from 1ドル$ to 10ドル^6$ --- strengths of the standard abilities.
The fifth line contains an integer $p_u$ (2ドルn \le p_u \le 12$) --- the number of ultimate abilities in the pool.
The sixth line contains $p_u$ integers from 1ドル$ to 10ドル^6$ --- strengths of the ultimate abilities.
Output a single integer --- the difference of strengths of the teams after all ability picks.
1 1 1 2 2 1 2 5 3 2 7 2
3
1 2 2 1 1 2 2 1 4 4 8 8 9 2 6 7
2
2 1 1 3 4 2 2 4 3 1 6 1 4 4 8 9 11 5 14 11 10 8 5
-1