题目描述

题目译自 Open Olympiad in Informatics 2020 Day2 T1 「Реалити-шоу / Reality Show」。

一档著名的真人秀节目正在为其第三季招募参与者！有 $n$ 名候选人通过了面试，编号从 $1$ 到 $n$。第 $i$ 名候选人的竞争力为 $l_i$，要聘请这位候选人，节目组需要支付 $s_i$ 卢布。

真人秀的主持人按编号从小到大（从 $i=1$ 到 $i=n$）依次浏览候选人的档案，并决定是否选中每位候选人参加节目。如果候选人 $i$ 的竞争力严格高于任何已选中的候选人的竞争力，则主持人肯定不会选择候选人 $i$。否则，主持人可以自行决定是否选择该候选人。主持人希望以最大化 利润 的方式选择参与者。

该真人秀的收入机制如下。对于每个竞争力值 $v$，都有一个对应的收入值 $c_v$，可能是正数也可能是负数。被选中的参与者将按编号从小到大的顺序依次上台。每当编号为 $i$ 的参与者上台时，会发生以下情况：

• 节目组赚取 $c_{l_i}$ 卢布，其中 $l_i$ 是该参与者的初始竞争力。
• 如果舞台上存在两个具有相同竞争力值的参与者，他们会立即开始打斗。打斗的结果如下：
  • 失败者将被救护车送走，退出项目；
  • 胜者的竞争力增加 $1$，节目组赚取 $c_t$ 卢布，其中 $t$ 是胜者新的竞争力值。
• 舞台上的打斗会持续进行，直到舞台上的所有参与者具有不同的竞争力值为止。

主持人希望选择参与者以最大化利润，利润定义为舞台上发生的所有收入总和减去邀请参与者的总成本（即选中参与者的 $s_i$ 之和）。帮助主持人使节目利润最大化！

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 2000)$，分别表示候选人数量和候选人初始竞争力的最大值。

第二行包含 $n$ 个整数 $l_i$ $(1 \leq l_i \leq m)$，表示每个候选人的竞争力。

第三行包含 $n$ 个整数 $s_i$ $(0 \leq s_i \leq 5000)$，表示聘请每个候选人需要支付的卢布数。

第四行包含 $n + m$ 个整数 $c_i$ $(|c_i| \leq 5000)$，表示每个竞争力值的收入水平。

保证在给定限制下，参与者的竞争力值不会超过 $n + m$。

输出格式

输出一个整数，即节目的最大利润。

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

6

在第一个样例中，选择编号为 $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$ 卢布。

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

2

在第二个样例中，无法同时邀请两个候选人，因为第二个候选人的竞争力更高，因此选择编号为 $1$ 的候选人更为有利。

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

62

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。