热门真人秀第三季正在招募新演员!编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 候选人已接受面试。候选人 $$$i$$$ 的攻击性级别为 $$$l_i$$$,招募该候选人将花费 $$$s_i$$$ 卢布。
节目主持人通过增加指数来审查从$$$i=1$$$到$$$i=n$$$的所有候选人的申请,并针对每个候选人决定是否招募该候选人。如果候选人 $$$i$$$ 的攻击性水平严格高于任何已接受的候选人,则候选人 $$$i$$$ 肯定会被拒绝。否则,主办方可以自行决定接受或拒绝该候选人。主持人要选择演员阵容,以求总利润最大化。
该节目的收入如下。对于每个积极性级别 $$$v$$$ 指定相应的盈利能力值 $$$c_v$$$,该值可以是正值也可以是负值。所有招募的参赛者,通过指数递增的方式,一一进入该阶段。当参与者 $$$i$$$ 进入舞台时,事件将按如下方式进行:
- 该节目制作 $$$c_{l_i}$$$ 卢布,其中 $$$l_i$$$ 是参与者 $$$i$$$ 的初始攻击性水平。
- 如果舞台上有两个攻击性水平相同的参与者,他们会立即开始打架。结果是:失败的参赛者住院并离开演出。 获胜参与者的攻击性级别增加 1,并且该节目赚取 $$$c_t$$$ 卢布,其中 $$$t$$$ 是新的攻击性级别。
- 战斗持续进行,直到舞台上的所有参与者都具有明显的攻击性水平。
允许选择一组空的参与者(不选择任何候选人)。
主持人希望招募演员,使总利润最大化。利润的计算方法是舞台活动的总收入减去招募所有接受的参与者的总费用(即他们的总 $$$s_i$$$)。帮助主持人让节目尽可能盈利。
输入
第一行包含两个整数 $$$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$$$。
输出
打印一个整数——该节目的最大利润。
示例
输入 #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
注意
在第一个示例案例中,最佳招募候选人 $$$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$$$。