← 返回题目列表

Codeforces · 1089/L

L. 懒惰乐园

中文机器翻译题面 查看原题

Lazyland 王国是 $$$n$$$ 闲人的家园。这些闲人非常懒惰,给他们的统治者,强大的懒惰之国国王带来了许多问题。

今天应该执行王国的 $$$k$$$ 重要工作 ($$$k \le n$$$)。每项工作都应该由一个人完成,每个人最多只能做一项工作。国王允许每个闲人选择一项他们想做的工作,第 $$$i$$$ 个闲人选择了工作 $$$a_i$$$。

不幸的是,有些工作可能不是任何人都可以选择的,所以国王必须说服一些闲人选择其他工作。国王知道说服第 $$$i$$$ 个闲人需要 $$$b_i$$$ 分钟。他要求劳工部长计算出说服闲人完成所有工作所需的最少总时间。你能帮助他吗?

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — 闲置工数量和作业数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le k$$$) - 每个惰轮选择的作业。

输入的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 国王说服第 $$$i$$$ 个闲人所需花费的时间。

输出

输出的唯一一行应该包含一个数字——国王说服闲人完成所有工作所需花费的最短总时间。

示例

输入
复制

8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2

输出
复制

10

输入
复制

3 3
3 1 2
5 3 4

输出
复制

0

注意

在第一个示例中,最佳计划是说服闲置者 1、6 和 8 去做工作 2、4 和 6。

在第二个例子中,每项工作都是由某个闲人选择的,因此无需说服任何人。