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$로 나눈 나머지 $r$이 $\{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로 선언하면 오버플로우가 발생할 수 있으니 주의하라.