Maximum Order Volume (Weighted Interval Scheduling)

A supermarket receives n calls in one day. Each call has a start time start, a duration duration, and an order volume volume. Choose non-conflicting calls to maximize the total order volume. Following the source's implementations in three languages, call intervals are half-open [start, start+duration): when one call ends exactly when the next one starts, both calls can be taken back to back.

Original constraints: 1≤n≤100000, 1≤start[i], duration[i], volume[i]≤10^9.

输入格式

The first line contains n; the next three lines contain the n values of start, duration, and volume, respectively.

输出格式

Output the maximum total order volume that can be obtained.

样例 1

输入：

5
10 5 15 18 30
30 12 20 35 35
50 51 20 25 10

输出：

76

样例说明

Sort by end time. Let dp[i] be the maximum order volume using the first i calls; when choosing call i, binary search for the number p of calls whose end time is no later than its start time, and the transition is max(dp[i-1], dp[p]+volume[i]).