12929번 - 빌딩 높이

문제

오늘은 천나라에 빌딩 N개를 새로 만들려고 한다. 새로운 빌딩은 일렬로 놓여져 있어야 하고, 차례대로 1번부터 N번까지 번호를 붙인다.

천나라에는 다음과 같이 새로운 빌딩에 대한 높이 제한이 있다.

• 모든 빌딩의 높이는 음이 아닌 정수이어야 한다.
• 빌딩 1의 높이는 0이다.
• 인접한 두 빌딩의 높이의 차이는 K보다 작거나 같아야 한다.
• 빌딩 X[i]의 높이는 T[i]보다 작거나 같아야 한다.

천나라의 높이 제한을 지키면서, 지을 수 있는 가장 큰 높이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 1,000,000,000)

둘째 줄에는 X와 T의 크기 M이 주어진다. (0 ≤ M ≤ min(N, 500))

M이 0이상일 경우 셋째 줄에는 X[i]가, 넷째 줄에는 T[i]가 주어진다. (1 ≤ X[i] ≤ N, 1 ≤ T[i] ≤ 1,000,000,000, X[i] < X[i+1]) M이 0인 경우에는 셋째 줄과 넷째 줄이 주어지지 않는다.

출력

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

제한

힌트