Reality Show

Time limit2sMemory limit1024 MB

Summary

Pick a subset of candidates that obeys the record rule, then maximize the on-stage fight revenue minus the recruitment costs.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

A popular reality show is recruiting a new cast for its third season. $n$ candidates numbered from $1$ to $n$ have been interviewed. Candidate $i$ has aggressiveness level $l_i$ , and recruiting this candidate costs the show $s_i$ roubles.

The host reviews the applications from $i=1$ to $i=n$ in index order and decides whether to recruit each candidate. If the aggressiveness level of candidate $i$ is strictly higher than that of every already accepted candidate, candidate $i$ is rejected automatically. Otherwise, the host may accept or reject the candidate as she wishes. The host wants to choose the cast that maximizes the total profit.

The show earns revenue as follows. For each aggressiveness level $v$ , a profitability value $c_v$ is given, which can be positive or negative. All recruited participants enter the stage one by one in index order. When participant $i$ enters the stage, the following happens.

The show earns $c_{l_i}$ roubles, where $l_i$ is the initial aggressiveness level of participant $i$ .
If two participants on stage have the same aggressiveness level, they fight immediately. The defeated participant is hospitalized and leaves the show. The victor's aggressiveness level increases by one, and the show earns $c_t$ roubles, where $t$ is the new level.
Fights continue until all participants on stage have distinct aggressiveness levels.

The host wants to recruit the cast that maximizes total profit. Profit is the total revenue from events on stage minus the total recruitment cost (the sum of all accepted $s_i$ ). Help the host make the show as profitable as possible.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 2000$ ), the number of candidates and an upper bound for the initial aggressiveness levels.

The second line contains $n$ integers $l_i$ ( $1 \le l_i \le m$ ), the initial aggressiveness levels of all candidates.

The third line contains $n$ integers $s_i$ ( $0 \le s_i \le 5000$ ), the cost in roubles to recruit each candidate.

The fourth line contains $n + m$ integers $c_i$ ( $|c_i| \le 5000$ ), the profitability for each aggressiveness level.

It is guaranteed that the aggressiveness level of any participant never exceeds $n + m$ under the given conditions.

Output

Print a single integer, the largest profit the show can make.

Hint

In the first sample, it is optimal to recruit candidates $1$ , $2$ , $3$ , and $5$ . Then the show pays $1 + 2 + 1 + 1 = 5$ roubles in recruitment. The events on stage proceed as follows.

A participant with aggressiveness level $4$ enters, and the show makes $4$ roubles.
A participant with aggressiveness level $3$ enters, and the show makes $3$ roubles.
A participant with aggressiveness level $1$ enters, and the show makes $1$ rouble.
Another participant with aggressiveness level $1$ enters, and the show makes $1$ rouble. A fight starts. One participant leaves, and the other rises to level $2$ , which earns the show an extra $2$ roubles.

Total revenue is $4 + 3 + 1 + 1 + 2 = 11$ roubles, so the profit is $11 - 5 = 6$ roubles.

In the second sample, the show cannot recruit both candidates because the second one has a higher aggressiveness level. It is better to recruit only candidate $1$ .

Examples3

Example 1

Input

5 4
4 3 1 2 1
1 2 1 2 1
1 2 3 4 5 6 7 8 9

Expected output

Example 2
Input
```
2 2
1 2
0 0
2 1 -100 -100
```
Expected output
```
2
```

Example 3

Input

5 4
4 3 2 1 1
0 2 6 7 4
12 12 12 6 -3 -5 3 10 -4

Expected output