Kayaks and the Strong Wind

Interview

Time limit1sMemory limit128 MB

Summary

Given broken and spare-carrying teams in a line, assign each spare kayak to an adjacent broken team to minimize the number of teams left unable to start.

Level: Medium4 of 10
Topics: Greedy, Brute force, Simulation
Solved: No attempts yet

Problem

Sanggeun held a kayak competition. Right before it began, a strong wind swept across the venue and broke some teams' kayaks, and the race must start immediately.

Fortunately, some teams brought one extra kayak just in case. A kayak is very heavy and hard to carry, so a team can lend its spare kayak only to the team that races immediately before or after it. That is, team 4 can lend its spare kayak only to team 3 or team 5. A kayak borrowed from another team cannot be lent onward to yet another team. Also, if a team that brought a spare has its own original kayak broken, that team must compete using its own spare kayak, and this kayak cannot be lent to any other team.

Given the teams whose kayaks are broken and the teams that brought a spare kayak, write a program that lends the kayaks appropriately so that the number of teams unable to start is minimized, and finds that minimum.

Input

The first line contains the number of teams N, the number of teams whose kayak is broken S, and the number of teams that brought a spare kayak R. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N)

The second line contains the numbers of the teams whose kayaks are broken. Team numbers are distinct.

The third line contains the numbers of the teams that brought a spare kayak. Team numbers are distinct.

Output

Print the minimum number of teams that cannot start on the first line.

Examples3

Example 1
Input
```
5 2 1
2 4
3
```
Expected output
```
1
```
Example 2
Input
```
5 2 3
2 4
1 3 5
```
Expected output
```
0
```
Example 3
Input
```
2 1 1
1
2
```
Expected output
```
0
```