Description

Jerry Prince 是一名四年级学生，他去 New-Lodnon 参观最受欢迎的游乐园 "The World's Start"。

他到达的机场就在地铁线的第一站旁边。这条地铁线有 $n$ 个站点，"The World's Start" 位于最后一个站点。New-Lodnon 的地铁非常快，所以你可以假设从一个站到下一个站只需要一分钟。

Jerry 需要一张地铁通行卡才能使用地铁。每张通行卡都有一个范围 $r$ 和一个价格 $p$。使用范围为 $r$ 的通行卡，Jerry 一次最多可以旅行 $r$ 个站。因此，如果 Jerry 在第 $i$ 个站进入地铁，他应该在从 $i - r$ 到 $i + r$ 的某个站点下车。需要 $d_{i}$ 分钟才能在第 $i$ 个站点下车并重新进入地铁。在第一站进入或最后一站下车不需要时间。

Jerry 不是很富有，但他有一些空闲时间，所以他决定购买最便宜的通行卡，使他能够在不超过 $t$ 分钟的时间内从第一站旅行到最后一站。

Input Format

输入文件的第一行包含两个整数 $n$ 和 $t$ —— 站点的数量和最大可能的时间 $(2 \le n \le 50 000$ ; $n - 1 \le t \le 10^{9})$。

第二行包含 $n - 1$ 个整数 $p_{r}$ —— 范围为 $r = 1$ 到 $n - 1$ 的通行卡的价格 $(1 \le p_{r} \le 100 000)$。

第三行包含 $n - 2$ 个整数 $d_{i}$ —— 在第 $i = 2$ 到 $n - 1$ 站点重新进入地铁所需的分钟数 $(1 \le d_{i} \le 10^{5})$。

Output Format

输出一个整数 $p$ —— 允许 Jerry 在不超过 $t$ 分钟内从第一站到最后一站的最便宜的通行卡的价格。

4 4
1 2 3
1 4

2

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。