样例下载

题目描述

有 N 个物品，第 i 个物品的体积为为 $A_i$。

有 N 个背包，第 i 个背包的体积为 $B_i$。

现在要把所有的物品全部装入到背包中。由于物品怕碰，一个背包只能装一个物品。每个物品不可分割，一个物品只能被装入到一个背包中。背包的体积不小于物品的体积，才能将该物品装入。

物品全部装入背包后，你要携带所有的背包离开。背包的总体积太大将会非常不方便。因此你希望所有背包的体积之和尽可能小。

幸运的是，你可以更改一些背包的体积为任意值。不过，你最多只能更改 K 个背包的体积。

问：如何操作可以使得你携带的所有背包的体积之和（记为 S）尽可能小？

你只需要输出最小的 S 值？

如果无法将全部物品都装入背包，则输出 -1.

输入

第一行：两个整数 N, K.

第二行：N 个整数 $B_i$

第三行：N 个整数 $A_i$

输出

一个整数，表示答案。

样例1输入

5 2
10 3 7 2 5
3 5 9 4 6

样例1输出

28

样例1解释

将 10 更改为 9，将 2 更改为 4.

装载方案为（背包-物品）：9-9, 3-3, 7-6, 4-4, 5-5

样例2输入

3 1
1 2 3
4 5 6

样例2输出

-1

数据范围

$1 ≤ K ≤ N ≤ 5×10^5, 1 ≤ A_i, B_i ≤ 10^9$