分数: 366 分
问题陈述
在高桥居住的小镇上,有 N 樱花斑呈直线排列,编号为Spot 1, 现货 2, \ldots, 现货 N 按顺序。相邻景点有长廊连接,有长廊 i (1 \leq i \leq N - 1) 连接点 i 和现货 总共 i + 1。有 N - 1 长廊。
每个点 j (1 \leq j \leq N) 有一个分数 P_j 代表该地点樱花的美丽。此外,每条海滨长廊 i (1 \leq i \leq N - 1) 有维护成本 C_i.
高桥计划维持一段连续的长廊以创建步行路线。具体来说,他选择整数 l, r (1 \leq l \leq r \leq N - 1)并维护所有长廊 l,长廊 l+1, \ldots,长廊 r。通过这样做,他可以访问 现货 全部 现货数量 l, 现货 l+1, \ldots, 现货 r+1 沿着维护好的长廊作为他的步行路线。
的 树的 满意 从步行路线中获得的 被定义为步行路线的分数总和 课程中包含的 r - l + 2 点:
P_l + P_{l+1} + \cdots + P_{r+1}
另一方面, 总成本 的维护是:
C_l + C_{l+1} + \cdots + C_r
高桥的预算是 B,他只能选择 (l, r) 使得总成本最多为 B。高桥必须准确选择并维持这样一个区间。
在所有方式中选择 (l, r) 使得总成本最多为 B,找到 满意度最大值.
需要注意的是,由于限制,每个长廊的维护成本最多为 B,所以 l = r (仅维持一条长廊)始终满足条件,并且至少存在一个有效选择 (l, r).
约束
- 2 \leq N \leq 5 \times 10^5
- 1 \leq B \leq 10^{14}
- 1 \leq P_j \leq 10^9 (1 \leq j \leq N)
- 1 \leq C_i \leq B (1 \leq i \leq N - 1)
- 所有输入值均为整数
输入
N B
P_1 P_2 \ldots P_N
C_1 C_2 \ldots C_{N-1}
- 第一行包含一个整数 N 代表樱花斑点的数量和一个整数 B 代表预算,以空格分隔。
- 第二行包含 N 整数 P_1, P_2, \ldots, P_N 代表每个点的分数,以空格分隔。
- 第三行包含 N - 1 整数 C_1, C_2, \ldots, C_{N-1} 代表每个长廊的维护成本,以空格分隔。
输出
在一行中打印所有维护间隔中总成本最多为最大的满意度 B.
示例输入 1
5 10 3 1 4 1 5 2 3 4 5
示例输出 1
10
示例输入 2
4 3 10 20 30 40 1 2 3
示例输出 2
70
示例输入 3
10 15 5 8 3 10 7 2 9 6 4 11 3 2 5 1 4 6 2 3 7
示例输出 3
35
示例输入 4
20 50 12 5 18 3 15 9 20 7 14 6 11 8 19 2 16 10 4 13 17 1 3 7 2 8 1 5 4 6 9 3 7 2 8 1 5 4 6 9 3
示例输出 4
130
示例输入 5
2 100000000000000 1000000000 1000000000 1
示例输出 5
2000000000