/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は山道のハイキングコースに挑戦します。
このハイキングコースには N 個のチェックポイントがあり、チェックポイント 1 から N まで番号が付けられています。コースは一本道であり、高橋君はチェックポイント 1 からスタートし、チェックポイント 1, 2, 3, \ldots, N の順に進みます。高橋君は好きなチェックポイントでハイキングを終了できます。つまり、途中のチェックポイントでそれ以上先に進まずに終了してもよいですし、チェックポイント N まで進んでもよいです。
各チェックポイント i（1 \leq i \leq N）には「景観スコア」 S_i が設定されています。高橋君がチェックポイント i に到達すると、景観スコア S_i を得ます。一方、チェックポイント i からチェックポイント i+1 へ移動するには体力コスト C_i（1 \leq i \leq N-1）がかかります。
高橋君は、いずれかのチェックポイント k（1 \leq k \leq N）でハイキングを終了します。このとき、高橋君の「ハイキングの満足度」は次の式で計算されます：
\left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)
すなわち、チェックポイント 1 から k までで得られる景観スコアの合計から、チェックポイント 1 から k に到達するまでにかかる体力コストの合計を引いた値です。k = 1 の場合、移動は発生しないため体力コストの合計は 0 となり、満足度は S_1 です。
高橋君がハイキングを終了するチェックポイントを最適に選んだとき、「ハイキングの満足度」の最大値を求めてください。
制約
- 1 \leq N \leq 10^6
- 1 \leq S_i \leq 10^9（1 \leq i \leq N）
- 1 \leq C_i \leq 10^9（1 \leq i \leq N-1）
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_{N-1}
- 1 行目には、チェックポイントの数を表す整数 N が与えられる。
- 2 行目には、各チェックポイントの景観スコアを表す N 個の整数 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
- 3 行目には、隣接するチェックポイント間の体力コストを表す N-1 個の整数 C_1, C_2, \ldots, C_{N-1} がスペース区切りで与えられる。ここで C_i はチェックポイント i からチェックポイント i+1 への移動にかかる体力コストである。ただし、N = 1 の場合、3 行目は空行になる。
出力
「ハイキングの満足度」の最大値を 1 行で出力してください。
入力例 1
5 5 3 8 2 6 4 10 1 3
出力例 1
6
入力例 2
4 10 1 1 1 100 100 100
出力例 2
10
入力例 3
12 7 15 3 20 6 8 25 4 10 12 5 18 5 12 4 30 2 7 20 1 15 3 9
出力例 3
25
入力例 4
20 13 8 21 5 34 2 18 27 6 11 40 3 16 9 25 7 30 4 14 22 6 20 4 10 30 1 15 35 2 8 12 25 5 18 3 28 7 9 11
出力例 4
66
入力例 5
1 1000000000
出力例 5
1000000000
Score : 300 pts
Problem Statement
Takahashi is going to attempt a mountain trail hiking course.
This hiking course has N checkpoints, numbered from checkpoint 1 to N. The course is a single path, and Takahashi starts at checkpoint 1 and proceeds in the order of checkpoints 1, 2, 3, \ldots, N. Takahashi can end the hike at any checkpoint he likes. That is, he may stop at an intermediate checkpoint without proceeding further, or he may go all the way to checkpoint N.
Each checkpoint i (1 \leq i \leq N) has a "scenery score" S_i assigned to it. When Takahashi reaches checkpoint i, he gains the scenery score S_i. On the other hand, moving from checkpoint i to checkpoint i+1 costs a stamina cost of C_i (1 \leq i \leq N-1).
Takahashi ends the hike at some checkpoint k (1 \leq k \leq N). At that point, Takahashi's "hiking satisfaction" is calculated by the following formula:
\left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)
In other words, it is the total scenery scores gained from checkpoints 1 through k, minus the total stamina cost required to travel from checkpoint 1 to checkpoint k. When k = 1, no movement occurs, so the total stamina cost is 0, and the satisfaction is S_1.
Find the maximum value of "hiking satisfaction" when Takahashi optimally chooses the checkpoint at which to end the hike.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
- All inputs are integers.
Input
The input is given from standard input in the following format.
N
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_{N-1}
- The first line contains an integer N representing the number of checkpoints.
- The second line contains N integers S_1, S_2, \ldots, S_N separated by spaces, representing the scenery scores of each checkpoint.
- The third line contains N-1 integers C_1, C_2, \ldots, C_{N-1} separated by spaces, representing the stamina costs between adjacent checkpoints. Here, C_i is the stamina cost for moving from checkpoint i to checkpoint i+1. However, when N = 1, the third line is an empty line.
Output
Output the maximum value of "hiking satisfaction" in a single line.
Sample Input 1
5 5 3 8 2 6 4 10 1 3
Sample Output 1
6
Sample Input 2
4 10 1 1 1 100 100 100
Sample Output 2
10
Sample Input 3
12 7 15 3 20 6 8 25 4 10 12 5 18 5 12 4 30 2 7 20 1 15 3 9
Sample Output 3
25
Sample Input 4
20 13 8 21 5 34 2 18 27 6 11 40 3 16 9 25 7 30 4 14 22 6 20 4 10 30 1 15 35 2 8 12 25 5 18 3 28 7 9 11
Sample Output 4
66
Sample Input 5
1 1000000000
Sample Output 5
1000000000