Задача №113635. Доставка футболок
Завершилась Командная Интернет-олимпиада Новой Зеландии по Алгоритмам (КИНЗА). После олимпиады оргкомитет принял решение отправить футболки всем призерам олимпиады. Доставка футболок была поручена компании, в которой работает курьер Билл.
Биллу требуется доставить \(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, \dots, z_{n−1}\), где \(z_0\) — это время, которое требуется Биллу, чтобы доехать от офиса до первого адресата, а \(z_i\) — это время, которое требуется Биллу для преодоления пути от \(i\)-го до \(i \ + \ 1\)-го адресата. Все \(z_i\) не превосходят \(10^4\).
В третьей строке находятся \(n\) неотрицательных целых чисел \(s_1, \ s_2, \dots, s_n \ (0 \le s_i \le 10^9\) ), где \(s_i\) — это момент, начиная с которого \(i\)-й адресат готов принять посылку. Билл начинает свой путь в момент времени 0.
Выведите одно число — минимальное время, за которое Билл сможет выполнить свое задание.
В примере Билл приезжает к первому адресату в момент времени 1 и сразу же передает ему посылку. В момент времени 2 он выезжает от первого адресата и в момент времени 7 приезжает ко второму. Он ждет его 3 минуты, до момента времени 10, но тот не появляется, поэтому Билл отправляется к третьему адресату и приезжает к нему в момент 14. Тот дома и принимает посылку. Таким образом, Билл освобождается в момент времени 15.
3 3 1 1 5 4 1 11 7
15