Max Sum of Non-Overlapping Intervals

Interval i is the closed interval [start[i],start[i]+duration[i]] with profit cost[i]. Choose pairwise non-overlapping intervals to maximize the total profit; sharing an endpoint also counts as overlapping, and choosing nothing is allowed. This closed-interval convention is restored from the source example, in which [2,4] and [4,7] are incompatible and the answer is 9.

输入格式

The first line contains n, followed by three lines: start, duration and cost. The original text had no numeric bounds; this site uses 1≤n≤200000, 0≤each value≤10^9; duration=0 means a single-point interval.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
4 2 7 8
3 2 3 2
7 3 1 2

输出：

9

样例 2

输入：

2
0 1
1 1
5 7

输出：

7

样例 3

输入：

3
1 1 2
0 0 0
3 5 4

输出：

9

样例说明

The answers are 9, 7 and 9. In the second example the intervals intersect at 1, so they cannot both be chosen; in the third example, of the two points at the same position choose the one with profit 5, then choose position 2 with profit 4.