CF1322D.Reality Show

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.

一档热门真人秀节目正在为第三季招募新演员！共有 $n$ 名候选人，编号从 $1$ 到 $n$，均已接受面试。候选人 $i$ 的攻击性等级为 $l_i$，招募该候选人需花费节目组 $s_i$ 卢布。

节目主持人按编号递增顺序（即从 $i = 1$ 到 $i = n$）逐一审核所有候选人的申请，并对每位候选人决定是否招募。若候选人 $i$ 的攻击性等级 严格高于 所有已接受候选人的攻击性等级，则该候选人 必定被拒绝；否则，主持人可自行决定接受或拒绝该候选人。主持人希望选出一组演员，使得总利润最大化。

节目的收入机制如下：对每个攻击性等级 $v$，均指定一个对应的盈利值 $c_v$（该值可正可负）。所有被招募的参与者将按编号递增顺序依次登台。当参与者 $i$ 登台时，发生以下事件：

• 节目获得 $c_{l_i}$ 卢布收入，其中 $l_i$ 是参与者 $i$ 初始的攻击性等级；
• 若此时舞台上存在两名（或以上）具有相同攻击性等级的参与者，则他们立即开始搏斗。搏斗结果如下：
  • 失败者被送医并退出节目；
  • 胜利者的攻击性等级提升 $1$，且节目获得 $c_t$ 卢布收入，其中 $t$ 是该胜利者提升后的新攻击性等级；
• 搏斗持续进行，直至舞台上所有参与者均具有互不相同的攻击性等级为止。

允许选择空集（即不招募任何候选人）。

主持人希望招募一组演员，使得总利润最大化。总利润定义为：舞台上所有事件带来的总收入，减去招募所有被接受候选人所需支付的总费用（即所有被接受者的 $s_i$ 之和）。请帮助主持人使节目利润最大化。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$）—— 分别表示候选人的数量以及初始攻击性水平的上界。

第二行包含 $n$ 个整数 $l_i$（$1 \le l_i \le m$）—— 表示所有候选人的初始攻击性水平。

第三行包含 $n$ 个整数 $s_i$（$0 \le s_i \le 5000$）—— 表示招募每位候选人所需的费用（单位：卢布）。

第四行包含 $n + m$ 个整数 $c_i$（$|c_i| \le 5000$）—— 表示每个攻击性水平对应的收益。

在给定条件下，保证任何参与者的攻击性水平均不会超过 $n + m$。

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

输出一个整数——演出的最大利润。

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$.

在第一个样例中，最优策略是招募候选人 $1, 2, 3, 5$。此时节目组需支付的招募费用为 $1 + 2 + 1 + 1 = 5$ 卢布。舞台上的事件将按如下方式展开：

• 一名攻击性等级为 $4$ 的参与者登上舞台，节目组获得 $4$ 卢布；
• 一名攻击性等级为 $3$ 的参与者登上舞台，节目组获得 $3$ 卢布；
• 一名攻击性等级为 $1$ 的参与者登上舞台，节目组获得 $1$ 卢布；
• 一名攻击性等级为 $1$ 的参与者登上舞台，节目组获得 $1$ 卢布，此时发生斗殴。其中一名参与者离场，另一名参与者的攻击性等级提升至 $2$。节目组因此额外获得 $2$ 卢布。

节目的总收入为 $4 + 3 + 1 + 1 + 2 = 11$ 卢布，利润为 $11 - 5 = 6$ 卢布。

在第二个样例中，由于第二位候选人的攻击性更高，因此无法同时招募两位候选人；故最优策略是仅招募候选人 $1$。