7. Odolateľná reklama

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¹ 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². 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³.

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.