Експрес-лінія
У Павла є іграшкова залізниця, яка має просту структуру. Вона складається з головної лінії, що включає станції, пронумеровані послідовно від 0 до n − 1 у напрямку лінії. Відстань між станціями з номерами i та i + 1 дорівнює l[i] сантиметрів (0 ≤ i < n − 1).
Окрім головної лінії, існують кілька другорядних ліній. Кожна з них складається з однієї ділянки, що з'єднує станцію на головній лінії з новою станцією, яка не належить до головної лінії. Ці нові станції не мають номерів. Від кожної станції на головній лінії може починатися не більше однієї другорядної лінії. Довжина другорядної лінії, що починається на станції з номером i, дорівнює d[i] сантиметрів. Якщо другорядна лінія відсутня, то d[i] = 0.
Павло планує побудувати одну додаткову ділянку залізниці: експрес-лінію між двома різними (можливо сусідніми) станціями на головній лінії. Довжина експрес-лінії буде рівно c сантиметрів, незалежно від вибраних станцій.
Кожна ділянка залізниці, включаючи нову експрес-лінію, може використовуватися в обох напрямках. Відстань між двома станціями визначається як мінімальна довжина шляху між ними вздовж ділянок залізниці. Діаметр залізниці — це максимальна з усіх відстаней між парами станцій. Іншими словами, це найменше число t, таке що відстань між будь-якими двома станціями не перевищує t.
Завдання Павла — побудувати експрес-лінію так, щоб підсумковий діаметр був якомога меншим.
Вхідні дані
Перший рядок містить цілі числа n та c (2 ≤ n ≤ 10^6, 1 ≤ c ≤ 10^9).
Другий рядок містить цілі числа l[0], ..., l[n − 2] (1 ≤ l[i] ≤ 10^9).
Третій рядок містить цілі числа d[0], …, d[n − 1] (0 ≤ d[i] ≤ 10^9).
Вихідні дані
Виведіть одне ціле число — найменший можливий діаметр.
Приклад 1
Оптимальне рішення — побудувати експрес-лінію між станціями 1 та 3, як показано нижче.
