Kekoland 是一个拥有 n 个美丽城市的国家,从左到右依次编号,并由 n - 1 条道路连接。第 i 条路连接城市 i 和 i+1,这条路的长度为 wi 公里。
当您在 Kekoland 开车时,每次您开车到达城市 i 时,您都会立即收到 gi 升汽油。在 Kekoland 没有其他方式获取天然气。
Kekoland 总裁 Keko 聘请您来组织 Kekoland 有史以来最美丽的比赛。让竞赛在城市 l 和 r 之间进行(l ≤ r)。比赛将分为两个阶段。在第一阶段,汽车将从城市 l 行驶到城市 r。完成第一赛段后,第二天将进行第二赛段,此时赛车手将驾驶自己的赛车从R到L。当然,由于这是一场比赛,赛车手直接从出发城市开车到终点城市。这意味着在第一阶段他们只会向右走,在第二阶段他们只会向左走。 l 和 r 之间的比赛的美丽程度等于 r - l + 1,因为赛车手将看到 r - l + 1 个美丽的 Kekoland 城市。汽车有无限的油箱,因此赛车手将消耗所有给他们的汽油。
在每个赛段开始时,参赛者以空油箱(0 升汽油)开始比赛。比赛开始后,他们将立即在出发城市(l为第一赛段,r为第二赛段)取走汽油。
如果赛车在到达终点之前耗尽汽油,则可能无法组织 l 和 r 之间的比赛。
你有 k 件礼物。每次你向城市 i 赠送一份礼物,它的值 gi 就会增加 1。你可以以任何方式在城市之间分配礼物(也可以向一个城市赠送很多礼物,每次 gi 都会增加 1)。您能组织的最美丽的比赛是什么?
每辆车每公里消耗 1 升汽油。
输入
输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 100 000, 0 ≤ k ≤ 109)——分别是 Kekoland 中的城市数量和你拥有的礼物数量。
下一行包含 n - 1 个整数。其中第 i 个是 wi (1 ≤ wi ≤ 109) — 城市 i 和 i + 1 之间的道路长度。
下一行包含 n 个整数。其中第 i 个是 gi (0 ≤ gi ≤ 109)——每次进入城市 i 时收到的 Gas 量。
输出
打印一行 — 您可以组织的最美丽的比赛之美。
示例
输入 #1
4 4 2 2 2 1 1 1 1
输出 #1
4
输入 #2
8 5 2 2 2 3 7 3 1 1 3 1 5 4 0 2 5
输出 #2
7
注意
在第一个示例中,如果您向每个城市赠送一份礼物,则可以在城市 1 和城市 4 之间进行比赛。
在第二个示例中,您应该在 g5 中添加 1,在 g6 中添加 4,然后就可以在城市 2 和 8 之间进行比赛。