Crossings of Crossings

Interview

Time limit2sMemory limit1024 MB

Summary

Find the fewest crossings needed to walk from house 0 on the left side to house f on the right side, given the crossings on each side and across the avenue.

Level: Medium4 of 10
Topics: BFS, Shortest path, Graph
Solved: No attempts yet

Problem

Zhele must reach the city office of the Transylvania hotel. The route runs along a long avenue with many intersections, including T-shaped ones (where one side street is missing).

To help Zhele find the way, the zombies gave him a schematic map. All houses are numbered in order. Houses on opposite sides of the avenue share the same number. The map also marks every crossing on the avenue. There are three types of crossings:

Along the left side of the avenue. A crossing lies between two houses and is given by the smaller house number $x$ . Crossing $x$ connects houses $x$ and $x + 1$ .
Along the right side of the avenue. A crossing lies between two houses and is given the same way.
Across the avenue. It lets you go from one side to the other, and it lies between two houses on opposite sides. It is given by the number of those houses.

Zhele starts at house 0 on the left side. He can move toward higher or lower house numbers. The office is on the right side at house $f$ .

Zhele hates crossings, so he wants to minimize the number of crossings he uses on the way.

Input

The first line contains three natural numbers $n$ , $m$ , $k$ ( $1 \le n, m, k \le 10^5$ ): the number of crossings of the first, second, and third type.

The second line contains $n$ integers $a_i$ ( $0 \le a_i \le 10^5$ ): the crossings on the left side of the avenue.

The third line contains $m$ integers $b_i$ ( $0 \le b_i \le 10^5$ ): the crossings on the right side of the avenue.

The fourth line contains $k$ integers $c_i$ ( $0 \le c_i \le 10^5$ ): the crossings across the avenue.

The fifth line contains one integer $f$ ( $0 \le f \le 10^5$ ): the house number Zhele is heading to.

Output

Print one line with the minimum number of crossings Zhele must use to reach the office.

Examples2

Example 1
Input
```
1 1 1
2
3
2
1
```
Expected output
```
1
```
Example 2
Input
```
4 3 3
1 4 5 8
8 9 11
0 7 15
14
```
Expected output
```
4
```