빌딩 높이

빌딩 $N$개를 일렬로 새로 짓는다. 왼쪽부터 차례대로 1번부터 $N$번까지 번호를 붙인다.

빌딩 높이에는 다음 제한이 있다.

• 모든 빌딩의 높이는 음이 아닌 정수이다.
• 1번 빌딩의 높이는 0이다.
• 이웃한 두 빌딩의 높이 차이는 $K$ 이하이다.
• $X_i$번 빌딩의 높이는 $T_i$ 이하이다.

제한을 모두 지키면서 지을 수 있는 가장 높은 빌딩의 높이를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $K$가 주어진다. ($1 \le N, K \le 10^9$)

둘째 줄에 높이 제한이 걸린 빌딩의 개수 $M$이 주어진다. ($0 \le M \le \min(N, 500)$)

$M$이 1 이상이면 셋째 줄에 $X_1, X_2, \dots, X_M$이, 넷째 줄에 $T_1, T_2, \dots, T_M$이 공백으로 구분되어 주어진다. ($1 \le X_i \le N$, $1 \le T_i \le 10^9$, $X_i < X_{i+1}$) $M$이 0이면 셋째 줄과 넷째 줄은 주어지지 않는다.

제한을 모두 지키면서 지을 수 있는 가장 높은 빌딩의 높이를 출력한다.