Експрес-лінія#7977
У Павла є іграшкова залізниця, яка має просту структуру. Вона складається з головної лінії, що включає станції, пронумеровані послідовно від до n - 1 у напрямку лінії. Відстань між станціями з номерами та i + 1 дорівнює l_i сантиметрів (0 \leq i < n - 1).
Окрім головної лінії, існують кілька другорядних ліній. Кожна з них складається з однієї ділянки, що з'єднує станцію на головній лінії з новою станцією, яка не належить до головної лінії. Ці нові станції не мають номерів. Від кожної станції на головній лінії може починатися не більше однієї другорядної лінії. Довжина другорядної лінії, що починається на станції з номером , дорівнює d_i сантиметрів. Якщо другорядна лінія відсутня, то d_i = 0.
Павло планує побудувати одну додаткову ділянку залізниці: експрес-лінію між двома різними (можливо сусідніми) станціями на головній лінії. Довжина експрес-лінії буде рівно сантиметрів, незалежно від вибраних станцій.
Кожна ділянка залізниці, включаючи нову експрес-лінію, може використовуватися в обох напрямках. Відстань між двома станціями визначається як мінімальна довжина шляху між ними вздовж ділянок залізниці. Діаметр залізниці — це максимальна з усіх відстаней між парами станцій. Іншими словами, це найменше число , таке що відстань між будь-якими двома станціями не перевищує .
Завдання Павла — побудувати експрес-лінію так, щоб підсумковий діаметр був якомога меншим.
Перший рядок містить цілі числа та (2 \leq n \leq 10^6, 1 \leq c \leq 10^9).
Другий рядок містить цілі числа l_0, \ldots, l_{n-2} (1 \leq l_i \leq 10^9).
Третій рядок містить цілі числа d_0, \ldots, d_{n-1} (0 \leq d_i \leq 10^9).
Виведіть одне ціле число — найменший можливий діаметр.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Оптимальне рішення — побудувати експрес-лінію між станціями та , як показано нижче.
