京都大学プログラミングコンテスト2015

D - 高橋君の旅行


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君はハイカラシティを旅している. ハイカラシティは 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

Source name

京都大学プログラミングコンテスト2015

Submit提出する