78 stairs descent contest

Interview

Time limit1sMemory limit1024 MB

Summary

Find the maximum total score of a path from step 1 to step N, where opening chest i needs the previous visited step to be at least H_i+B_i tall.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search, Array
Solved: No attempts yet

Problem

In the distant future, POSTECH campus kept expanding to fit the growing number of freshmen. As a result, many facilities became far larger than before. In particular, the 78 stairs went through repeated construction and became a huge staircase made of $N$ steps. Steps are numbered from 1 to $N$ , and the height of step $i$ is $H_i$ . Since these are stairs, the heights decrease monotonically with the step number.

Future POSTECH students found the best use for these 78 stairs, and it is the 78 stairs descent contest. A contestant starts at step 1 and keeps moving down to steps with larger numbers until reaching step $N$ . Contestants may skip steps, but they cannot move to a step with a smaller number. Every step except step 1 holds one treasure chest. Step $i$ has a treasure chest with score $A_i$ and durability $B_i$ . To open the chest on step $i$ and earn its score, the height of the step visited just before must be at least $H_i+B_i$ .

Your goal is to win the contest by earning the highest score. Given the score and durability of each chest, find the maximum score you can earn.

Input

The first line contains the number of steps $N$ ( $2 \le N \le 300,000$ ).

The second line contains $N$ integers $H_1, H_2, \cdots, H_N$ separated by spaces, giving the height of each step ( $0 \le H_i \le 10^9$ ; $H_i \ge H_{i+1}$ ).

The third line contains $N-1$ integers $A_2, A_3, \cdots, A_N$ separated by spaces, giving the score of the chest on each step ( $0 \le A_i \le 10^9$ ).

The fourth line contains $N-1$ integers $B_2, B_3, \cdots, B_N$ separated by spaces, giving the durability of the chest on each step ( $0 \le B_i \le 10^9$ ).

Output

Print the maximum score that can be earned.

Examples3

Example 1
Input
```
5
10 8 5 3 1
1 2 3 4
1 5 1 8
```
Expected output
```
5
```
Example 2
Input
```
3
5 1 1
5 1
5 0
```
Expected output
```
1
```
Example 3
Input
```
4
4 3 2 1
10 10 10
5 5 5
```
Expected output
```
0
```