← 返回题目列表

AtCoder · kupc2015_d

D. 高桥的旅行

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

問題文

高桥正在灰卡拉市旅行。 光市是 它由 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