Ability Draft

Time limit2sMemory limit512 MB

Summary

Given a pick order and ability strengths, find the optimal difference between two teams' total strengths when players draft standard and ultimate abilities in turn.

Level: Hard8 of 10
Topics: Bit manipulation, Dynamic programming, Game theory
Solved: No attempts yet

Problem

Dota 2 is a competitive multiplayer computer game. Two teams of $n$ players fight each other 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 mode of Dota 2. At the start of the game, each player receives a random hero with no abilities. Players then pick abilities in a fixed order from the pool provided by the game. On his turn, a player may pick any remaining standard ability, or, if he has not yet picked his ultimate ability, any remaining ultimate ability. 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 a team is the sum of the strengths of all abilities of all heroes on that team. Every player picks abilities so that, when the draft ends, the difference between his team's strength and the enemy team's strength is as large as possible.

Given the strengths of the abilities in the pool and the pick order, find the difference between the two teams' strengths when all players pick optimally.

Input

The first line contains two integers $n$ and $s$ ( $1 \le n \le 5$ , $1 \le s \le 3$ ), the number of players in each team and the number of standard abilities per hero.

The second line contains $2n \cdot (s + 1)$ player indices, the pick order. Each index from $1$ to $2n$ appears exactly $s + 1$ times in this array. Players with indices from $1$ to $n$ belong to the first team, and players with indices from $n + 1$ to $2n$ belong to the second team.

The third line contains an integer $p_s$ ( $2n \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$ , the strengths of the standard abilities.

The fifth line contains an integer $p_u$ ( $2n \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$ , the strengths of the ultimate abilities.

Output

Output a single integer, the difference between the two teams' strengths after all picks when every player picks optimally.

Examples3

Example 1
Input
```
1 1
1 2 2 1
2
5 3
2
7 2
```
Expected output
```
3
```
Example 2
Input
```
1 2
2 1 1 2 2 1
4
4 8 8 9
2
6 7
```
Expected output
```
2
```

Example 3

Input

2 1
1 3 4 2 2 4 3 1
6
1 4 4 8 9 11
5
14 11 10 8 5

Expected output

-1