問題文
高桥正在灰卡拉市旅行。 光市是 它由 N+1 城镇组成。 那些城市 我们称之为 1, 街 2, ..., 街 N+1 。
高桥君 N 我决定计划一日游。 高桥的 1 当天开始时您拥有的金额为 0 和城市 我在 1 。 i ( i = 1, ..., N ) 在这一天,执行以下操作之一。
- 我现在所在的城市 k 从城市出发 转至 k+1 。这时候你手上的钱就是 A_k 改变。 留在
- 我现在所在的城市 k 。这时候你手上的钱就是 B_k 改变。 留在
高桥决定制定一个满足以下条件的旅行计划。
- i ( i = 1, ..., N ) 你的钱到最后不会是负数。
- N 当日结束时的最大金额
这样的旅行 N 查找并打印当天结束时您拥有的金额。
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 ... A_N B_1 B_2 ... B_N
- 1 行是一个整数 给出 N ( 2 \leq N \leq 10^5 )。
- 2 在线 N 整数由空格分隔。 第 i 个整数是 A_i ( -10^9 \leq A_i \leq 10^9 )。
- 3 在线 N 整数由空格分隔。 第 i 个整数是 B_i ( 0 \leq B_i \leq 10^9 )。
出力
高桥计划的旅行 N 打印当天结束时您拥有的钱。
部分点
如果满足以下约束的数据集的所有答案都是正确的, 3 给出了点的部分点。
- N \leq 10^2
入力例1
3 -1 -1 -1 1 0 0
出力例1
3
整天城市 如果您停留在 1 ,您将在最后获得最大金额。
入力例2
3 -1 -1 -1 1 10 0
出力例2
10
1 日是城 留在 1 , 移至2 日是城 留在 2 , 留在3 日是城 留在 2 ,那么最后的金额就是最大的。 我无法从
入力例3
3 -1 10 10 0 10 100
出力例3
0
街 1 搬走,最后我的钱是 有 0 。
入力例4
12 1 2 1 1 4 2 3 1 0 6 6 1 0 0 1 1 1 2 1 3 0 0 1 1
出力例4
30