← 返回题目列表

AtCoder · awc0089_c

C. 步行赏樱

中文机器翻译题面 查看原题

分数: 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