Переходы переходов

시간 제한2초메모리 제한1024 MB

요약

대로 양쪽에 놓인 횡단보도와 도로를 가로지르는 횡단보도가 주어질 때, 왼쪽 0번 집에서 오른쪽 f번 집까지 가는 데 필요한 최소 횡단보도 수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 최단 경로, 그리디
정답자: 아직 제출이 없습니다

문제

Чтобы добраться до офиса городского представительства отеля <<Трансельвания>> Желе нужно преодолеть непростой путь, а именно пройти по длинному проспекту с множеством перекрестков в том числе Т-образных (у которых отсутствует один боковой проезд).

Чтобы Желе было легче ориентироваться, Зомби выдали ему схематическую карту, на которой последовательно пронумерованы все дома. При этом номера противоположных домов, стоящих на разных сторонах проспекта, совпадают. Также на карте отмечены все переходы дорог, которые есть на проспекте. Переходы бывают трех типов:

Вдоль проспекта на левой его стороне. Переход расположен между двумя домами и задается минимальным номером дома, между которыми он находится. Так переход задающийся числом $x$ проходит между домами с номерами $x$ и $x + 1$ .
Вдоль проспекта на правой его стороне. Переход также расположен между двумя домами и задается аналогично.
Переход поперек проспекта. Позволяет перейти с одной стороны на другую, и расположен между двумя противоположными домами. Задается номером этих домов.

Желе начинает свой путь у дома с номером ноль, находящегося с левой стороны проспекта. Желе может двигаться как в порядке увеличения номеров домов, так и в порядке уменьшения. Офис находится на правой стороне в доме с номером $f$ .

Желе ненавидит переходы, поэтому хочет минимизировать количество использований переходов на своем пути.

입력

В первой строке входного файла дано три натуральных числа $n, m, k$ ( $1 \le n, m, k \le 10^5$ ) --- количество переходов первого, второго и третьего типа соответственно.

Во второй строке дано $n$ чисел $a\_i$ ( $0 \le a\_i \le 10^5$ ) --- числа задающие переходы на левой стороне проспекта.

В третьей строке дано $m$ чисел $b\_i$ ( $0 \le b\_i \le 10^5$ ) --- числа задающие переходы на правой стороне проспекта.

В четвертой строке дано $k$ чисел $c\_i$ ( $0 \le c\_i \le 10^5$ ) --- числа задающие переходы поперек проспекта.

В пятой строке дано число $f$ ( $0 \le f \le 10^5$ ) --- номер дома, в который направляется Желе.

출력

В единственной строке выходного файла выведите наименьшее количество раз, которым Желе придется воспользоваться переходами при движении до офиса.

예제2

예제 1
입력
```
1 1 1
2
3
2
1
```
예상 출력
```
1
```
예제 2
입력
```
4 3 3
1 4 5 8
8 9 11
0 7 15
14
```
예상 출력
```
4
```