AT_abc358_d [ABC358D] Souvenirs

题目描述

AtCoder Land 的纪念品商店里有 $N$ 个箱子出售。

每个箱子编号为 $1, 2, \ldots, N$，第 $i$ 个箱子的价格为 $A_i$ 日元，并且里面装有 $A_i$ 个点心。

高桥君打算从这 $N$ 个箱子中选出 $M$ 个箱子买回家，并将这 $M$ 个箱子分别分给编号为 $1, 2, \ldots, M$ 的 $M$ 个人，每人一个箱子。

不过，高桥君希望能够满足以下条件：

• 对于每个 $i = 1, 2, \ldots, M$，第 $i$ 个人分到的箱子中必须至少有 $B_i$ 个点心。

请注意，不能把两个以上的箱子分给同一个人，也不能把同一个箱子分给多个人。

请判断是否可以恰当地购买 $M$ 个箱子使得上述条件成立。如果可以，请求出高桥君需要支付的最小总金额。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

如果可以恰当地购买 $M$ 个箱子使得条件成立，则输出高桥君需要支付的最小总金额。否则输出 $-1$。

输入输出样例 #1

输入 #1

4 2
3 4 5 4
1 4

输出 #1

7

输入输出样例 #2

输入 #2

3 3
1 1 1
1000000000 1000000000 1000000000

输出 #2

-1

输入输出样例 #3

输入 #3

7 3
2 6 8 9 5 1 11
3 5 7

输出 #3

19

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• 输入的所有数均为整数

样例解释 1

高桥君可以购买箱子 $1$ 和 $4$，将箱子 $1$ 分给第 $1$ 个人，箱子 $4$ 分给第 $2$ 个人，这样可以满足条件。此时高桥君支付的总金额为 $7$ 日元，且无法用更少的钱满足条件，因此输出 $7$。

由 ChatGPT 4.1 翻译