Migrated from Lutece 2793 痛，太痛了

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

佛耶戈没有走出他的满眼破败，就像 “我” 逃不掉满脑的谎言。 “还会再见吗，燕子，再见的时候你要幸福，好不好？。” “你的世界以后没有我了，没关系你要自己幸福！” “燕子！燕子！没有你我怎么活啊，燕子！” 燕子要走了，去洋国，我不甘心，不甘心……“我” 要把燕子追回来。 ——回忆 现在燕子到机场了，“我” 得马上过去，但是 “我” 没有太多钱，还好 “我” 有特权可以买VIP地铁票，只要 “我” 坐到最后一站就可以找到：燕子啦！ 现在有 $N$ 个地铁站，全部按照线性排列。有 $N - 1$ 种 VIP 地铁票，每张地铁票都有一个范围 $r$ 和一个票价 $P$, 第 $r$ 种地铁票的价格为 $P_r$，且每次最多可以坐 $r$ 个站。同时票可以无限使用并且只能购买一张，若乘坐地铁到达了限定的距离，就要出站。想要重新使用就得再进站，这样就得花费 $D_i$ 的时间。给定每个站坐一站需要花费一个单位时间，需要从第一个站坐到最后一个站。 请问 “我” 在离飞机起飞剩下的 $T$ 时间内到达最后一个站的最便宜 VIP 票的票价是多少。 当然这种问题要请不是舔狗的你才能想清楚啦。想不清楚，没事，你也要幸福。

Input

第一行，输入包含两个整数 $N$ 和 $T$，分别表示地铁站的数目和限定的总时间。
第二行，包含 $N - 1$个整数 $P_r$，表示距离为 $r$ 的 VIP 票票价。
第三行，包含 $N - 2$个整数 $D_i$，表示第 $i$ 个站进出站的时间。$(i = 2...n - 1)$

Output

输出一个整数 $P$，表示最低的VIP票价，使得能在 $T$ 时间内坐到最后一个地铁站。

Samples

4 4
1 2 3
1 4

2

Constraints

$2\leq n \leq 50000$
$n - 1\leq T \leq 10^9$
$1\leq P_r \leq 100000$
$1\leq d_i \leq 10^5$

Resources

2022 UESTC ICPC Training for Dynamic Programming