CF1322D Reality Show

一档热门真人秀正在为第三季招募新成员！共有 $n$ 位候选人，编号从 $1$ 到 $n$。第 $i$ 位候选人的攻击性等级为 $l_i$，招募该候选人需要花费 $s_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, 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$ 位候选人。 由 ChatGPT 4.1 翻译