分数: 300 分
问题陈述
高桥打算尝试山路徒步路线。
这个徒步路线有 N 检查点,从检查点开始编号 1 to N。路线是单线,高桥从检查站出发 1 并按检查点顺序进行 1, 2, 3, \ldots, N。高桥可以在他喜欢的任何检查站结束徒步旅行。也就是说,他可能会停在一个中间检查点而不再继续前进,或者他可能会一直走到检查点 N.
每个检查点 i (1 \leq i \leq N) 有一个“风景分数” S_i 分配给它。当高桥到达检查站时 i,他获得风景分数 S_i。另一方面,从检查站出发 i 前往检查点 i+1 消耗体力消耗 C_i (1 \leq i \leq N-1).
高桥在某个检查站结束徒步 k (1 \leq k \leq N)。此时,高桥的“徒步满意度”由以下公式计算:
\left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)
也就是说,是通过关卡获得的风景总分 1 通过 k,减去从检查站出发所需的总体力消耗 1 前往检查点 k。当 k = 1,没有发生任何移动,因此总体力消耗为 0,满意度为 S_1.
求高桥最优选择结束徒步的检查点时“徒步满意度”的最大值。
约束
- 1 \leq N \leq 10^6
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
- 所有输入均为整数。
输入
输入由以下格式的标准输入给出。
N
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_{N-1}
- 第一行包含一个整数 N 代表检查点的数量。
- 第二行包含 N 整数 S_1, S_2, \ldots, S_N 以空格分隔,代表每个关卡的风景分数。
- 第三行包含 N-1 整数 C_1, C_2, \ldots, C_{N-1} 以空格分隔,代表相邻检查点之间的体力消耗。在这里, C_i 是从检查点移动的耐力消耗 i 前往检查点 i+1。然而,当 N = 1,第三行是空行。
输出
在单行中输出“徒步满意度”的最大值。
示例输入 1
5 5 3 8 2 6 4 10 1 3
示例输出 1
6
示例输入 2
4 10 1 1 1 100 100 100
示例输出 2
10
示例输入 3
12 7 15 3 20 6 8 25 4 10 12 5 18 5 12 4 30 2 7 20 1 15 3 9
示例输出 3
25
示例输入 4
20 13 8 21 5 34 2 18 27 6 11 40 3 16 9 25 7 30 4 14 22 6 20 4 10 30 1 15 35 2 8 12 25 5 18 3 28 7 9 11
示例输出 4
66
示例输入 5
1 1000000000
示例输出 5
1000000000