Рабочее место участника

Завершилась Командная Интернет-олимпиада Новой Зеландии по Алгоритмам (КИНЗА). После олимпиады оргкомитет принял решение отправить футболки всем призерам олимпиады. Доставка футболок была поручена компании, в которой работает курьер Билл.

Биллу требуется доставить `n` футболок. Он должен доставлять посылки в том порядке, в котором они значатся в его обходном листе. При этом, если посылку доставить не удалось, то в обходном листе ставится отказ, и Билл едет по следующему адресу.

Билл начинает свой рабочий день в офисе компании в момент 0. Приезжая к адресату посылки, он ждет не более `k` минут, и если за это время адресат открывает дверь, то Билл отдает ему посылку, процесс передачи посылки без учета времени ожидания занимает `t` минут. Если же в течение `k` минут дверь не открывается и получатель не появляется, то Билл едет дальше. При этом, если получатель появился ровно ровно через `k` минут после приезда Билла, то Билл успевает это заметить, и посылка оказывается доставлена. Рабочий день Билла заканчивается, когда он заканчивает передавать последнюю посылку, либо отмечает в обходном листе отказ от ее получения.

Начальник Билла Джон хочет проверить, насколько добросовестно тот работает. Джону известно, сколько времени ему потребуется на то, чтобы доехать от офиса до первого адресата, а также время на переезд от очередного адресата до следующего. Кроме того, он провел телефонный опрос и знает время, начиная с которого каждый из получателей футболок будет дома. Теперь Джон хочет узнать, в какой момент Билл закончит свой рабочий день.

В первой строке входного файла находятся три целых числа `n`, `k`, `t` (`1\ ≤\ n\ ≤\ 50\ 000`, `1\ ≤\ k,\ t\ ≤\ 10^4`).

Во второй строке находятся `n` натуральных чисел `z_0,\ z_1,\ …,\ z_{n-1}`, где `z_0` – это время, которое требуется Биллу, чтобы доехать от офиса до первого адресата, а `z_i` – это время, которое требуется Биллу для преодоления пути от `i`-го до `i+1`-го адресата. Все `z_i` не превосходят `10^4`.

В третьей строке находятся `n` неотрицательных целых чисел `s_1,\ s_2,\ …,\ s_n` (`0\ ≤\ s_i\ ≤\ 10^{9}`), где `s_i` – это момент, начиная с которого `i`-й адресат готов принять посылку. Билл начинает свой путь в момент времени 0.

Выведите одно число – минимальное время, за которое Билл сможет выполнить свое задание.

3 3 1
1 5 4
1 11 7

15

В примере Билл приезжает к первому адресату в момент времени 1 и сразу же передает ему посылку. В момент времени 2 он выезжает от первого адресата и в момент времени 7 приезжает ко второму. Он ждет его 3 минуты, до момента времени 10, но тот не появляется, поэтому Билл отправляется к третьему адресату и приезжает к нему в момент 14. Тот дома и принимает посылку. Таким образом, Билл освобождается в момент времени 15.