티셔츠 배달

뉴질랜드 알고리즘 인터넷 팀 올림피아드(KINZA)가 끝났다. 대회가 끝난 뒤 주최 측은 모든 수상자에게 티셔츠를 보내기로 했다. 티셔츠 배달은 택배 기사 빌이 다니는 회사에 맡겨졌다.

빌은 $n$장의 티셔츠를 배달해야 한다. 그는 자신의 배달 목록에 적힌 순서대로 소포를 배달해야 한다. 소포를 배달하지 못하면 목록에 거절을 표시하고 다음 주소로 간다.

빌은 시각 0에 회사 사무실에서 근무를 시작한다. 소포 수령인의 주소에 도착하면 그는 최대 $k$분을 기다리고, 그 안에 수령인이 문을 열면 소포를 건넨다. 기다리는 시간을 제외한 소포 전달 과정은 $t$분이 걸린다. $k$분 동안 문이 열리지 않고 수령인이 나타나지 않으면 빌은 다음으로 간다. 빌이 도착한 지 정확히 $k$분 뒤에 수령인이 나타나면 빌은 그것을 알아차리고 소포는 배달된다. 빌의 근무일은 마지막 소포를 전달하거나 목록에 수령 거절을 표시하면 끝난다.

빌의 상사 존은 빌이 얼마나 성실하게 일하는지 확인하려고 한다. 존은 사무실에서 첫 번째 수령인까지 가는 데 걸리는 시간과, 어떤 수령인에서 다음 수령인까지 이동하는 데 걸리는 시간을 알고 있다. 또한 전화 조사를 통해 티셔츠를 받는 사람마다 언제부터 집에 있는지도 알고 있다. 이제 존은 빌이 근무일을 언제 마치는지 알고 싶어 한다.

첫째 줄에 세 정수 $n$, $k$, $t$가 주어진다 ($1 \le n \le 50\,000$, $1 \le k, t \le 10^4$).

둘째 줄에 $n$개의 자연수 $z_0, z_1, \ldots, z_{n-1}$이 주어진다. $z_0$은 빌이 사무실에서 첫 번째 수령인까지 가는 데 걸리는 시간이고, $z_i$는 빌이 $i$번째 수령인에서 $i+1$번째 수령인까지 이동하는 데 걸리는 시간이다. 모든 $z_i$는 $10^4$을 넘지 않는다.

셋째 줄에 $n$개의 음이 아닌 정수 $s_1, s_2, \ldots, s_n$이 주어진다 ($0 \le s_i \le 10^{9}$). $s_i$는 $i$번째 수령인이 소포를 받을 준비가 되는 시각이다. 빌은 시각 0에 출발한다.

빌이 자신의 임무를 완수할 수 있는 최소 시간을 하나의 수로 출력한다.

예에서 빌은 시각 1에 첫 번째 수령인에게 도착해 곧바로 소포를 건넨다. 시각 2에 첫 번째 수령인을 떠나 시각 7에 두 번째 수령인에게 도착한다. 그는 3분을 기다려 시각 10이 되지만 수령인이 나타나지 않으므로 세 번째 수령인에게 가서 시각 14에 도착한다. 그 수령인은 집에 있고 소포를 받는다. 따라서 빌은 시각 15에 일을 마친다.