Ekspress xətti

Pavlinin oyuncaq dəmir yolu var və bu dəmir yolu çox sadə bir quruluşa malikdir. Yolun bir əsas xətti var və bu xətt boyunca ardıcıl olaraq 0-dan n − 1-ə qədər nömrələnmiş stansiyalar yerləşir. i və i + 1 nömrəli stansiyalar arasındakı məsafə l[i] santimetrdir (0 ≤ i < n − 1).

Əsas xəttdən başqa, bir neçə ikinci dərəcəli xətt də mövcuddur. Hər bir ikinci dərəcəli xətt, əsas xəttdəki bir stansiyanı və əsas xəttdə olmayan yeni bir stansiyanı birləşdirən bir dəmir yolu hissəsindən ibarətdir. Bu yeni stansiyaların nömrələri yoxdur. Əsas xəttdəki hər bir stansiyadan ən çox bir ikinci dərəcəli xətt başlaya bilər. i nömrəli stansiyadan başlayan ikinci dərəcəli xəttin uzunluğu d[i] santimetrdir. i stansiyasından başlayan ikinci dərəcəli yolun olmamasını göstərmək üçün d[i] = 0 istifadə olunur.

Pavlin indi iki fərqli (mümkün qonşu) əsas xəttdə yerləşən stansiyalar arasında bir əlavə dəmir yolu hissəsi - ekspress xətt qurmaq istəyir. Ekspress xətt, hansı iki stansiyanı birləşdirəcəyindən asılı olmayaraq, dəqiq c santimetr uzunluğunda olacaq.

Yeni ekspress xətt də daxil olmaqla, hər bir dəmir yolu hissəsi hər iki istiqamətdə istifadə edilə bilər. İki stansiya arasındakı məsafə, bir stansiyadan digərinə dəmir yolu hissələri boyunca keçən yolun minimal uzunluğudur. Dəmir yolunun diametri, stansiya cütləri arasındakı məsafələrin maksimumudur. Başqa sözlə, bu, elə bir ən kiçik t ədədi ki, hər hansı iki stansiya arasındakı məsafə t-dən çox deyil.

Pavlin ekspress xətti elə qurmaq istəyir ki, nəticədə alınan diametr mümkün qədər kiçik olsun.

Giriş məlumatları

Birinci sətir tam ədədlər n və c (2 ≤ n ≤ 10^6, 1 ≤ c ≤ 10^9) ehtiva edir.

İkinci sətir tam ədədlər l[0], ..., l[n − 2] (1 ≤ l[i] ≤ 10^9) ehtiva edir.

Üçüncü sətir tam ədədlər d[0], …, d[n − 1] (0 ≤ d[i] ≤ 10^9) ehtiva edir.

Çıxış məlumatları

Bir tam ədəd çıxarın - mümkün olan ən kiçik diametr.

Nümunə 1

Optimal həll, aşağıda göstərildiyi kimi, 1 və 3 stansiyaları arasında ekspress xətt qurmaqdır.