题目描述

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 \le n \le 50 000$ ; $n - 1 \le t \le 10^{9}).$

The second line contains $n - 1$ integers $p_{r}$ -- the prices of travel cards with range $r = 1$ . . . $n − 1 (1 \le p_{r} \le 100 000)$

The third line contains $n - 2$ integers $d_{i}$ -- the number of minutes required to reenter metro at stop $i = 2$ . . . $n - 1 (1 \le d_{i} \le 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.

题目大意

杰瑞在一条地铁线路上，这条线有$n$个站，世界的起点在最后一个，地铁很快，你可以在一分钟内从一个站点到达下一个站点。

杰瑞需要一张旅行卡才能乘地铁。每张旅行卡都有一个范围$r$和价格$p$。使用范围为$r$的旅行卡，他一次就只能最多旅行$r$站。因此，如果他在第二站进入地铁，他应该在$i−r$到$i+r$的其中一站下车。它需要$d[i]$在第一站下车或者重新进入地铁，不需要时间进入第一站或离开最后一站。

杰瑞不是很富有，但他有一些空闲时间，所以他决定买一张最便宜的旅行卡，这样他就可以在不超过$t$分钟的时间内从地铁的第一站坐到到最后一站。

4 4
1 2 3
1 4

2

提示

Time limit: 2 s, Memory limit: 256 MB.