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