CF671E Organizing a Race

Kekoland 是一个有 $n$ 个美丽城市的国家，这些城市从左到右编号，并由 $n-1$ 条道路连接。第 $i$ 条道路连接城市 $i$ 和城市 $i+1$，这条道路的长度为 $w_{i}$ 公里。 在 Kekoland 开车时，每当你驾驶到城市 $i$ 时，会立即获得 $g_{i}$ 升汽油。在 Kekoland，不能通过其他方式获取汽油。 你被 Kekoland 总统 Keko 雇佣，组织一场该国有史以来最美丽的比赛。假设比赛发生在城市 $l$ 和 $r$ 之间（$l \leq r$）。比赛包含两个阶段。第一阶段赛车从城市 $l$ 行驶到城市 $r$。完成第一阶段后，第二天进行第二阶段，此时赛车从城市 $r$ 行驶回城市 $l$。当然，作为比赛，赛车会直接从起点城市驶向终点城市，因此，第一阶段他们只向右行驶，第二阶段只向左行驶。比赛在 $l$ 和 $r$ 之间的美丽值定义为 $r-l+1$，因为赛车手能看到 $r-l+1$ 个美丽的城市。车辆的油箱容量无限，因此赛车手会全部获取到他们能得到的汽油。 每个阶段开始时，赛车的油箱都是空的（$0$ 升汽油），并会在起点城市（第一阶段为 $l$，第二阶段为 $r$）立即获得该城市的全部汽油量。 若车辆在到达终点前汽油耗尽，则无法在 $l$ 和 $r$ 之间组织比赛。 你有 $k$ 个礼物，每给城市 $i$ 一个礼物，该城市的 $g_{i}$ 增加 $1$。你可以任意分配这些礼物给各个城市（同一个城市可以获得多个礼物，每获得一个 $g_{i}$ 增加 $1$）。请问，最多可以组织美丽值为多少的比赛？ 每辆车每行驶一公里消耗 $1$ 升汽油。

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 100000$，$0 \leq k \leq 10^9$），分别表示 Kekoland 的城市数量和你拥有的礼物数量。 下一行包含 $n-1$ 个整数，第 $i$ 个为 $w_{i}$（$1 \leq w_{i} \leq 10^9$），表示第 $i$ 条道路的长度。 下一行包含 $n$ 个整数，第 $i$ 个为 $g_{i}$（$0 \leq g_{i} \leq 10^9$），表示每次你到达城市 $i$ 时可以获得的汽油量。

输出一行，表示你最多能组织的最美丽比赛的美丽值。

在第一个样例中，如果给每个城市各一个礼物，就可以在城市 $1$ 到城市 $4$ 之间举办一场比赛。 在第二个样例中，你应该将 $1$ 个礼物分配给城市 $5$，$4$ 个礼物分配给城市 $6$，这样就可以在城市 $2$ 和城市 $8$ 间举办比赛。 由 ChatGPT 5 翻译