← 返回题目列表

Codeforces · 779/C

C. 不诚实的卖家

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

Igor 在一家商店发现折扣,决定购买 n 件商品。商店的折扣将持续一周,伊戈尔知道每件商品现在的价格是ai,折扣一周后其价格将是bi。

并非所有卖家都是诚实的,因此现在某些产品可能比折扣后更贵。

Igor 决定现在至少购买 k 件商品,但要等待本周剩余时间,以便尽可能省钱。你的任务是确定 Igor 可以花最少的钱来购买所有 n 件物品。

输入

第一行有两个正整数 n 和 k (1 ≤ n ≤ 2·105, 0 ≤ k ≤ n) — 要购买的物品总数和 Igor 现在想要购买的物品的最小数量。

第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 104) — 折扣期间(即现在)商品的价格。

第三行包含整数序列 b1, b2, ..., bn (1 ≤ bi ≤ 104) — 折扣后(即一周后)商品的价格。

输出

打印 Igor 购买所有 n 件物品所需花费的最低金额。请记住,他现在应该至少购买 k 件物品。

示例

输入 #1

3 1
5 4 6
3 1 5

输出 #1

10

输入 #2

5 3
3 4 7 10 3
4 5 5 12 5

输出 #2

25

注意

在第一个示例中,Igor 应该支付 6 购买商品 3。但是他应该在一周后购买商品 1 和 2。他将为它们支付 3 和 1。所以他总共要支付 6 + 3 + 1 = 10。

在第二个示例中,Igor 现在应该购买商品 1、2、4 和 5,并分别支付 3、4、10 和 3。他应该在一周的折扣后购买第 3 件商品,他将支付 5 美元。他总共将花费 3 + 4 + 10 + 3 + 5 = 25。