Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Jerry Prince is the fourth grade student and he goes to New-Lodnon to visit the most popular amusement park "The World's Start". 

An airport he arrives at is next to the first stop of the metro line. This line has $n$ stops and "The World's Start" is on the last of them. The metro of New-Lodnon is pretty fast so you may assume that you can get  from a stop to the next one in just one minute.

Jerry needs a travel card to use the metro. Each travel card has a range $r$ and a price $p$. With a travel card of range $r$ Jerry may travel no more than $r$ stops at once. Therefore, if Jerry enters metro at the stop $i$ he should exit on one of the stops from $i - r$ to $i + r$ inclusive. It takes $d_i$ minutes to exit and reenter metro at $i$-th stop. There is no time required to enter the first stop or exit the last one.

Jerry is not very rich but he has some spare time, so he decided to buy the cheapest travel card that will allow him to travel from the first metro stop to the last one in no more than $t$ minutes.

The first line of the input file contains two integers $n$ and $t$ — the number of stops and the maximum possible time ($2 \leq n \leq 50\,000$; $n - 1 \leq t \leq 10^9$).

The second line contains $n - 1$ integers $p_r$ — the prices of travel cards with range $r = 1 \ldots n - 1$ ($1 \leq p_r \leq 100\,000$)

The third line contains $n - 2$ integers $d_i$ — the number of minutes required to reenter metro at stop $i = 2 \ldots n-1$ ($1 \leq d_i \leq 10^5$).

Output a single integer $p$ — the lowest possible price of one travel card that allows Jerry to travel from the first to the last stop in no more than $t$ minutes.