5731. 源石虫

单点时限: 1.0 sec

内存限制: 512 MB

JK 在玩一个横板2D游戏。游戏中有 $n(1\leq n \leq 2\times 10^6)$ 个源石虫,源石虫有类型 $1$ 和类型 $2$ 这两种类型。所有源石虫可以视作在 $x$ 轴上排成一列,第 $i$ 个源石虫在坐标 $x = i$ 处。

JK 从 $x = 0$ 处出发,不断向 $x$ 轴正方向走。每次遇到源石虫,她可以选择是否击杀源石虫,击杀第 $i$ 个源石虫后可以获得 $w_i (1\leq w_i \leq 10^9)$ 块金币。

每次击杀类型 $1$ 的源石虫后,就不能击杀随后的 $a(0 \leq a \leq n)$ 个源石虫中类型 $1$ 的源石虫。每次击杀类型 $2$ 的源石虫后,就不能击杀随后的 $b(0 \leq b \leq n)$ 个源石虫中类型 $2$ 的源石虫。

JK 最多能获得多少块金币?

输入格式

第一行,三个整数 $n, a, b$。

第二行,$n$ 个整数,第 $i$ 个整数 $w_i$ 表示击杀第 $i$ 个源石虫后可以获得的金币数。
第三行,$n$ 个整数,表示第 $i$ 个源石虫的类型。若为 $1$,则表示类型 $1$ 的源石虫,若为 $2$,则表示类型 $2$ 的源石虫。

输出格式

一个整数,表示 JK 最多能获得的金币数量。

样例

Input
9 2 3
10 2 2 5 4 1 1 1 9
1 1 1 1 2 2 1 2 2
Output
29

91 人解决,118 人已尝试。

102 份提交通过,共有 376 份提交。

3.6 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 1 周,1 天前.

来源: N/A

题目标签