Reality Show

题意翻译

### 题目大意 有 $n$ 个选手，每个选手有 $l_i$ 攻击力，录用这个选手花费 $s_i$ 的代价。每个攻击力对应一个权值 $c_i$。录用的选手按照编号从小到大出场。演出的收益计算方法如下： - 某个攻击力 $l$ 选手上场，获得收益 $c_l$; - 如果场上有两个攻击力相同的选手，那么他们会打一架，死掉一个选手，另一个选手攻击力 $+1$，并获得新攻击力对应的收益。重复以上操作直到场上所有选手攻击力**两两不同**。 求一个攻击力**单调不升**的选手序列，录用这个序列所对应的选手，**最大化**其收益减去代价的值 （一个也不选也是合法的）。

题目描述

A popular reality show is recruiting a new cast for the third season! $ n $ candidates numbered from $ 1 $ to $ n $ have been interviewed. The candidate $ i $ has aggressiveness level $ l_i $ , and recruiting this candidate will cost the show $ s_i $ roubles. The show host reviewes applications of all candidates from $ i=1 $ to $ i=n $ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $ i $ is strictly higher than that of any already accepted candidates, then the candidate $ i $ will definitely be rejected. Otherwise the host may accept or reject this candidate at her own discretion. The host wants to choose the cast so that to maximize the total profit. The show makes revenue as follows. For each aggressiveness level $ v $ a corresponding profitability value $ c_v $ is specified, which can be positive as well as negative. All recruited participants enter the stage one by one by increasing of their indices. When the participant $ i $ enters the stage, events proceed as follows: - The show makes $ c_{l_i} $ roubles, where $ l_i $ is initial aggressiveness level of the participant $ i $ . - If there are two participants with the same aggressiveness level on stage, they immediately start a fight. The outcome of this is: - the defeated participant is hospitalized and leaves the show. - aggressiveness level of the victorious participant is increased by one, and the show makes $ c_t $ roubles, where $ t $ is the new aggressiveness level. - The fights continue until all participants on stage have distinct aggressiveness levels. It is allowed to select an empty set of participants (to choose neither of the candidates). The host wants to recruit the cast so that the total profit is maximized. The profit is calculated as the total revenue from the events on stage, less the total expenses to recruit all accepted participants (that is, their total $ s_i $ ). Help the host to make the show as profitable as possible.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 2000 $ ) — the number of candidates and an upper bound for initial aggressiveness levels. The second line contains $ n $ integers $ l_i $ ( $ 1 \le l_i \le m $ ) — initial aggressiveness levels of all candidates. The third line contains $ n $ integers $ s_i $ ( $ 0 \le s_i \le 5000 $ ) — the costs (in roubles) to recruit each of the candidates. The fourth line contains $ n + m $ integers $ c_i $ ( $ |c_i| \le 5000 $ ) — profitability for each aggrressiveness level. It is guaranteed that aggressiveness level of any participant can never exceed $ n + m $ under given conditions.

输出格式

Print a single integer — the largest profit of the show.

输入输出样例

输入样例 #1

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

输出样例 #1

6

输入样例 #2

2 2
1 2
0 0
2 1 -100 -100

输出样例 #2

2

输入样例 #3

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

输出样例 #3

62

说明

In the first sample case it is optimal to recruit candidates $ 1, 2, 3, 5 $ . Then the show will pay $ 1 + 2 + 1 + 1 = 5 $ roubles for recruitment. The events on stage will proceed as follows: - a participant with aggressiveness level $ 4 $ enters the stage, the show makes $ 4 $ roubles; - a participant with aggressiveness level $ 3 $ enters the stage, the show makes $ 3 $ roubles; - a participant with aggressiveness level $ 1 $ enters the stage, the show makes $ 1 $ rouble; - a participant with aggressiveness level $ 1 $ enters the stage, the show makes $ 1 $ roubles, a fight starts. One of the participants leaves, the other one increases his aggressiveness level to $ 2 $ . The show will make extra $ 2 $ roubles for this. Total revenue of the show will be $ 4 + 3 + 1 + 1 + 2=11 $ roubles, and the profit is $ 11 - 5 = 6 $ roubles. In the second sample case it is impossible to recruit both candidates since the second one has higher aggressiveness, thus it is better to recruit the candidate $ 1 $ .