Problem Description

Takahashi is traveling in the HiKarashi City, which consists of $ N+1 $ towns. Let's call these towns Town $ 1 $, Town $ 2 $, ..., Town $ N+1 $.

Takahashi has decided to plan a trip for $ N $ days. At the beginning of the first day, he has $ 0 $ money and is in Town $ 1 $. On the $ i $ ($ i = 1, ..., N $) day, he will perform one of the following actions:

• Move from the current Town $ k $ to Town $ k+1 $. In this case, his money will change by $ A_k $.
• Stay in the current Town $ k $. In this case, his money will change by $ B_k $.

Takahashi has decided to make a trip plan that satisfies the following conditions:

• At the end of each day $ i $ ($ i = 1, ..., N $), his money does not become negative.
• The money at the end of the $ N $th day is maximized.

Output the money at the end of the $ N $th day for such a trip plan.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $ $ B_1 $ $ B_2 $ ... $ B_N $

• The first line contains an integer $ N $ ($2 \leq N \leq 10^5$).
• The second line contains $ N $ integers separated by spaces. The $ i $th integer is $ A_i $ ($-10^9 \leq A_i \leq 10^9$).
• The third line contains $ N $ integers separated by spaces. The $ i $th integer is $ B_i $ ($0 \leq B_i \leq 10^9$).

Output Format

Output the money Takahashi will have at the end of the $ N $th day of his planned trip.

Sample Input and Output

Sample Input #1

3
-1 -1 -1
1 0 0

Sample Output #1

3

Sample Input #2

3
-1 -1 -1
1 10 0

Sample Output #2

10

Sample Input #3

3
-1 10 10
0 10 100

Sample Output #3

0

Sample Input #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

Sample Output #4

30

Notes/Hints

Partial Points

If you solve all the datasets satisfying the following constraint correctly, you will be awarded $ 3 $ partial points:

• $N \leq 10^2$

见题面 Input 部分

见题面 Output 部分