Journey to "The World's Start"

Jerry Prince is a fourth grade student, and he is going to New-Lodnon to see "The World's Start", the most popular amusement park there.

The airport he lands at is next to the first stop of the metro line. The line has $n$ stops and "The World's Start" is at the last one. The metro of New-Lodnon is fast, so you may assume that a ride from one stop to the next takes exactly one minute.

Jerry needs a travel card to use the metro. Every travel card has a range $r$ and a price $p$. With a card of range $r$ Jerry may ride at most $r$ stops at once, so if he boards at stop $i$ he must get off at one of the stops from $i-r$ to $i+r$. Getting off and boarding again at stop $i$ takes $d_i$ minutes. Boarding at stop 1 and getting off at stop $n$ take no time.

Jerry is not rich but he has some spare time, so he decided to buy the cheapest travel card that lets him go from stop 1 to stop $n$ in at most $t$ minutes.

The first line contains two integers $n$ and $t$, the number of stops and the largest time he may spend ($2 \le n \le 50000$, $n-1 \le t \le 10^9$).

The second line contains $n-1$ integers $p_1, p_2, \dots, p_{n-1}$, where $p_r$ is the price of the travel card of range $r$ ($1 \le p_r \le 100000$).

The third line contains $n-2$ integers $d_2, d_3, \dots, d_{n-1}$, where $d_i$ is the number of minutes needed to get off and board again at stop $i$ ($1 \le d_i \le 100000$). When $n = 2$ this line is empty.

Print one integer, the lowest price of a single travel card that lets Jerry go from stop 1 to stop $n$ in at most $t$ minutes.