D - 高橋君の旅行
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はハイカラシティを旅している． ハイカラシティは 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