Souvenirs

题目描述

AtCoder Land 的纪念品商店出售 $N$ 个盒子。 这些盒子编号为 $1$ 到 $N$，第 $i$ 个盒子的价格为 $A_i$ 日元，并且包含 $A_i$ 颗糖果。 Takahashi 想从 $N$ 个盒子中购买 $M$ 个，并把每人分给编号为 $1,2,\ldots,M$ 的 $M$ 个人每人一盒。 这里，他想购买满足以下条件的盒子：

对于每个 $i = 1,2,\ldots,M$，编号为 $i$ 的人被分到的盒子中至少包含 $B_i$ 颗糖果。

注意不允许给某个人多于一盒，也不允许把同一个盒子分给多人。 判断是否存在可以满足条件的 $M$ 个可购买的盒子，如果存在，求出 Takahashi 需要支付的最少总金额。

输入格式

输入通过标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

如果存在可以满足条件的 $M$ 个可购买的盒子，打印 Takahashi 需要支付的最少总金额。否则，打印 $-1$。

4 2
3 4 5 4
1 4

7

3 3
1 1 1
1000000000 1000000000 1000000000

-1

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

19

提示

$1 \leq M \leq N \leq 2 \times 10^5$ $1 \leq A_i, B_i \leq 10^9$ 所有输入值均为整数。Takahashi 可以购买盒子 $1$ 和 $4$，并把盒子 $1$ 给第 1 号人，盒子 $4$ 给第 2 号人以满足条件。 在这种情况下，他总共需要支付 $7$ 日元，而且不可能支付少于 $7$ 日元仍满足条件，所以输出 $7$。

标签: AtCoder|abc358D

来源

AtCoder|abc358D