Jerry Prince 是一名四年级学生，他前往 New-Lodnon 参观最受欢迎的游乐园“The World’s Start”。

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

Jerry 需要一张交通卡来乘坐地铁。每张交通卡都有一个范围 $r$ 和一个价格 $p$。持有范围为 $r$ 的交通卡，Jerry 一次最多可以乘坐 $r$ 个站点。因此，如果 Jerry 在第 $i$ 站进入地铁，他应该在 $i$ 到 $i+r$ 之间的某个站点下车。在第 $i$ 站下车并重新进入地铁需要 $d_i$ 分钟。在第一站进入或在最后一站下车不需要额外时间。

Jerry 并不富裕，但他有一些空闲时间，因此他决定购买最便宜的交通卡，使得他能够在不超过 $t$ 分钟的时间内从第一站到达最后一站。

输入格式

第一行包含两个整数 $n$ 和 $t$ —— 站点数量和最大允许时间 ($2 \le n \le 50\,000$; $n - 1 \le t \le 10^9$)。

第二行包含 $n - 1$ 个整数 $p_r$ —— 范围为 $r = 1 \dots n - 1$ 的交通卡价格 ($1 \le p_r \le 100\,000$)。

第三行包含 $n - 2$ 个整数 $d_i$ —— 在第 $i = 2 \dots n - 1$ 站重新进入地铁所需的时间（分钟）($1 \le d_i \le 10^5$)。

输出格式

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

样例

输入格式 1

4 4
1 2 3
1 4

输出格式 1

2