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

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

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

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

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

Входные данные

Первая строка содержит целые числа n и c (2 ≤ n ≤ 106, 1 ≤ c ≤ 109).

Вторая строка содержит целые числа l0, ..., ln−2 (1 ≤ li ≤ 109).

Третья строка содержит целые числа d0, …, dn−1 (0 ≤ di ≤ 109).

Выходные данные

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

Пример 1

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