31941번 - 1D 게임

문제

SCSC에 갓 들어온 뉴비는 고인물들에게 자신의 실력을 보여주기 위해 게임을 개발했다!

뉴비가 개발한 게임은 간단하다. 캐릭터는 가장 왼쪽 끝의 0ドル$번부터 가장 오른쪽 끝의 $L$번까지 정수로 순서대로 번호가 매겨져 있으며 일렬로 놓여 있는 $L+1$개의 칸 위를 움직인다. 캐릭터는 0ドル$번 칸에서 출발해 매 턴마다 이동하여 $L$번 칸에 도달해야 한다. $K$개 칸에는 영구 발판이, 나머지 $L+1-K$개 칸에는 임시 발판이 놓여있다. 임시 발판은 특정 턴이 되면 잠시 사라졌다가 다시 생기면서 캐릭터를 떨어뜨려 패배하게 만든다. 이렇게 임시 발판이 사라지는 턴을 위험한 턴이라고 부른다. 시작점인 0ドル$번 칸과 도착점인 $L$번 칸에는 영구 발판이 놓여 있다.

각 턴은 다음과 같은 순서대로 진행된다. 턴 번호는 0ドル$부터 시작하고 캐릭터는 0ドル$번 칸에서 출발한다.

1. 캐릭터가 $L$번 칸에 있다면 승리하고 게임이 종료된다. 이때의 턴 번호를 승리 시간이라고 한다.
2. 현재 턴이 위험한 턴이면 모든 임시 발판이 사라졌다가 다시 생겨난다. 이때 캐릭터가 임시 발판이 있었던 칸에 있다면 아래로 떨어져 패배하고 게임이 종료된다.
3. 캐릭터는 현재 있는 칸에서 왼쪽 또는 오른쪽으로 1ドル$칸 이동하거나 그대로 머무른다. 0ドル$번 칸에서 왼쪽으로 이동할 수 없다.
4. 현재 턴이 종료되고 다음 턴이 시작되며 턴 번호가 1ドル$ 증가한다.

0ドル$번 턴부터 $T-1$번 턴까지 $N$개의 위험한 턴이 있고 턴 번호는 각각 $t_1,ドル $t_2,ドル $\cdots,ドル $t_N$번이다. 위험한 턴은 게임이 시작하는 0ドル$번 턴으로부터 $T$턴을 주기로 반복된다. 다시 말해 $t(t \geq 0)$를 $T$로 나눈 나머지 $r$가 $r \in \{ t_1, t_2, \cdots , t_N \}$를 만족하면 $t$번 턴은 위험한 턴이다. 예를 들어 $T=4,ドル $N=2,ドル $t_1 = 0,ドル $t_2 = 1$일 때 0ドル,ドル 1ドル,ドル 4ドル,ドル 5ドル,ドル 8ドル,ドル $\cdots$번 턴이 위험한 턴이다.

이제 뉴비는 게임의 로직을 모두 완성했다. 하지만 우리의 뉴비는 발판과 위험한 턴의 배열이 주어졌을 때 얼마나 빨리 승리할 수 있을지 잘 모른다. 여러분이 뉴비를 도와 얼마나 빨리 승리할 수 있을지 구해주자!

입력

첫째 줄에 정수 $T$와 $N$이 공백으로 구분되어 주어진다. $(1\leq T\leq 10^{12};$ 1ドル\leq N\leq 10^6;$ $N\leq T)$

둘째 줄에 정수 $L$과 $K$가 공백으로 구분되어 주어진다. $(1\leq L\leq 10^{12};$ 2ドル\leq K\leq 10^6;$ $K\leq L+1)$

셋째 줄에 0ドル$번 턴과 $T-1$번 턴 사이에 발생하는 $N$개의 위험한 턴의 번호 $t_1,ドル $t_2,ドル $\cdots,ドル $t_N$이 공백으로 구분되어 오름차순으로 주어진다. $(0 \leq t_i \leq T - 1)$

넷째 줄에 영구 발판이 놓인 $K$개 칸의 번호 $l_1,ドル $l_2,ドル $\cdots,ドル $l_K$가 공백으로 구분되어 오름차순으로 주어진다. $(0 \leq l_j \leq L;$ $l_1 = 0;$ $l_K = L)$

출력

가능한 승리 시간의 최솟값을 출력한다. 만약 유한 번의 턴 내에 승리할 수 없다면 What is that map newbie...를 출력한다.

$L$번 칸에 도달한 즉시 게임이 종료되는 것이 아니라 다음 턴이 시작된 후 과정 1.에서 게임이 종료됨에 유의하라.

제한

노트

C/C++, Java 등의 언어에서 일부 변수를 int로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.