eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Экспресс-линия

Экспресс-линия

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У Павла есть игрушечная железная дорога. Она очень просто устроена. У дороги есть одна главная линия, состоящая из станций, последовательно пронумерованных от 0 до n1 в порядке следования вдоль линии. Расстояние между станциями с номерами i и i + 1 равно l[i] сантиметров (0i < n1).

Кроме главной линии существуют несколько второстепенных. Каждая второстепенная линия состоит из одного участка железной дороги, соединяющего станцию на главной линии и новую станцию, которая не находится на главной линии. Эти новые станции не имеют номеров. От каждой станции на главной линии может начинаться не более одной второстепенной линии. Длина второстепенной линии, начинающейся в станции с номером i, равна d[i] сантиметров. Для обозначения отсутствия второстепенной дороги, начинающейся в станции i, используется d[i] = 0.

prb7977.gif

Теперь Павел хочет построить один дополнительный участок железной дороги: экспресс-линию между двумя различными (возможно соседними) станциями, расположенными на главной линии. Экспресс-линия будет иметь длину ровно c сантиметров, независимо от того, какие две станции она будет соединять.

Каждый участок железной дороги, включая новую экспресс-линию, может быть использован в обоих направлениях. Расстоянием между двумя станциями называется минимальная длина пути, который проходит от одной станции до другой вдоль участков железной дороги. Диаметром железной дороги называется максимальное из расстояний между парами станций. Другими словами, это наименьшее число t, такое что расстояние между любыми двумя станциями не больше чем t.

Павел хочет построить экспресс-линию таким образом, чтобы итоговый диаметр был как можно меньше.

Вхідні дані

Первая строка содержит целые числа n и c (2n10^6, 1c10^9).

Вторая строка содержит целые числа l[0], ..., l[n − 2] (1l[i]10^9).

Третья строка содержит целые числа d[0], …, d[n − 1] (0d[i]10^9).

Вихідні дані

Выведите одно целое число - наименьший возможный диаметр.

Пример 1

Оптимальное решение - построить экспресс-линию между станциями 1 и 3, как показано ниже.

prb7977_1.gif

Приклад

Вхідні дані #1
4 10
10 20 20
0 40 0 30
Вихідні дані #1
80
Вхідні дані #2
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
Вихідні дані #2
110
Вхідні дані #3
4 1
2 2 2
1 10 10 1
Вихідні дані #3
21
Вхідні дані #4
3 3
1 1
1 1 1
Вихідні дані #4
4
Джерело 2016 IOI Kazan, Russia, Day 1