该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

吉祥（ JiXiang ）因为在数字游戏中得到了你的帮助，所以马上成为 XJS Games 中令人们尊敬的王者。这次，他又带领游戏中的新手前往寻找“冰封的魔龙”—— 一个在航道终极站点的神秘存在。

题目描述

吉祥从“XJS港”出发，这里是通往“冰封的魔龙”所在的航道的第一站。航道总共有 $n$ 个站点，而“冰封的魔龙”所在的终极地点位于最后一个站点，航道非常快速，吉祥可以在一分钟内从一个站点到下一个。

吉祥需要一张航道通行卡才能使用这条航道。每张通行卡有一个范围 $r$ ，并且每张卡片都有相应的价格 $p$ 。吉祥可以选择适合的航道通行卡，在一次旅行中最多经过 $r$ 个站点。换句话说，假如他从第 $i$ 站进入航道，他可以选择从第 $i − r$ 到第 $i + r$ 的任意站点下船。重新进入航道需要在站点 $i$ 花费时间 $d_i$ ，但第一站和最后一站不需要额外时间。

吉祥并不富裕，吉祥希望购买一张最便宜的航道通行卡，以便在不超过 $t$ 分钟的时间内从第一站安全到达“冰封的魔龙”的终极站点。此时的他没有足够的时间来做出决策，所以，他又找到了你帮他解决问题。

输入格式

第一行包含两个整数 $n$ 和 $t$ 表示航道站点数和最大允许的时间。

第二行包含 $n − 1$ 个整数 $p_r(1≤p_r≤100000)$ 表示范围 $r = 1$ 到 $n − 1$ 的航道通行卡价格。

第三行包含 $n − 2$ 个整数 $d_i(1≤d_i≤10^5)$ 表示站点 $i = 2$ 到 $n − 1$ 的重新进入航道所需要的时间。

输出格式

输出一个整数 $p$ 表示使得阿瑞斯可以在不超过 $t$ 分钟的时间内从第一站到达“冰封的魔龙”所在的终极站点的最低航道通行卡价格。

输入输出样例 #1

输入 #1

4 4
1 2 3
1 4

输出 #1

2

说明/提示

数据范围：

$2≤n≤100000$

$n − 1≤t≤10^9$