Dopravný podnik vám prináša nový revolučný spôsob platenia za dopravu!!!

Kúpte si jeden z našich lístkov a jazdite už navždy[^1] bezplatne!!!

S $$k$$-zastávkovým lístkom sa môžete previezť, jednu, dve, dokonca až $$k$$ zastávok!!!

Kúpte si lístok už dnes a v cene dostanete aj vyhrievaný vankúšik, ktorý vám spríjemní čas strávený čakaním na zastávkach!!!

Reklama ťa zaujala množstvom výkričníkov. Vieš, že v nových električkách sú nové označovače lístkov so širšími otvormi a bolo treba upraviť formát lístkov. Okrem zmeny rozmeru však dopravný podnik zmenil aj typy lístkov a vymyslel aj novú, neodolateľnú marketingovú stratégiu, ktorej svedkom si, bohužiaľ, aj ty.

Keďže nemáš vodičák, používaš hromadnú dopravu. Každý deň sa cestou do školy prevezieš $$n$$ zastávok. Prvá zastávka je pri tvojom dome, posledná pri škole. Doteraz ti vyhovovala ročná električenka, ale tá ti práve vypršala a neostáva ti nič iné než si vybrať nejaký revolučný $$k$$-zastávkový lístok.

S týmto lístkom sa môžeš previezť najviac $$k$$ zastávok, no potom musíš vystúpiť a počkať na ďalší spoj[^2]. Na zastávke pri dome nikdy nečakáš, lebo vieš naspamäť časy, kedy ti chodia autobusy. Na poslednej zastávke tiež nemusíš čakať a môžeš sa hneď radostne rozbehnúť do školy[^3].

S vyhrievaným vankúšikom sa premôžeš a na zastávkach dokopy počkáš aj $$t$$ minút. Občas mávaš pri cestovaní spoločnosť, takže si hovoríš, že čakanie zvládneš. Preto si chceš kúpiť najlacnejší lístok, s ktorým budeš na ceste do školy čakať najviac $$t$$ minút. Šetríš si totiž na tú vec, ktorú si chceš už dlho kúpiť bez vedomia rodičov.

Úloha

Trasa má dĺžku $$n$$ – postupne prechádza zastávkami $$1, 2, \dots n$$. Pre každú zastávku $$2$$ až $$n-1$$ dostanete počet minút, ktorý sa na danej zastávke čaká na ďalší spoj. Tiež dostanete ceny $$k$$-zastávkových lístkov pre $$k = 1, 2, 3, \dots , n-1$$. Z ľubovoľnej zastávky s číslom $$z$$ sa dá s $$k$$-zastávkovým lístkom dostať na jednu jazdu na zastávky $$z-k$$ až $$z+k$$.

Celkovo si ochotný čakať najviac $$t$$ minút a chceš nájsť najlacnejší lístok, s ktorým sa dostaneš zo zastávky $$1$$ na zastávku $$n$$ s prestupovým čakaním najviac $$t$$.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve čísla $$n$$ a $$t$$ ($$2 \leq n \leq 100\, 000, 0 \leq t \leq 10^9$$) – dĺžka trasy a celkový čas, ktorý môžeš čakať na zastávkach. Na druhom riadku bude $$n-1$$ čísel $$c_k$$ ($$0 \leq c_k \leq 10^9$$) – cena $$k$$-zastávkového lístka pre $$k = 1, 2, 3, \dots , n-1$$. Na treťom riadku vstupu je $$n-2$$ čísel $$t_i$$ ($$0 \leq t_i \leq 10^9$$) – časy čakania na zastávkach $$2$$ až $$n-1$$.

Formát výstupu

Vypíšte jedno číslo – cenu najlacnejšieho lístka, s ktorým budete čakať na zastávkach dokopy najviac $$t$$ minút.

Príklad

Input:

6 9
1 42 9 2 54
5 6 5 4

Output:

2

S 1- alebo 2-zastávkovým lístkom by sme čakali pridlho, s 3-zastávkovým lístkom stačí čakať 5 minút, no lacnejší je 4-zastávkový, tak zoberieme ten.

1. Platí do ukončenia akcie.↩

2. Začínaš si do hĺbky uvedomovať, aký výborný nápad sú $$k$$-zastávkové lístky.↩

3. Ale komu sa chce behať, že?↩