CF797F Mice and Holes

有一天，Masha 回到家时发现走廊里有 $n$ 只老鼠。她大声喊叫，受惊的老鼠们开始奔向走廊上的洞穴。 可以将走廊表示为数轴，上面有 $n$ 只老鼠和 $m$ 个洞。第 $i$ 只老鼠在坐标 $x_{i}$ 处，第 $j$ 个洞的位置为 $p_{j}$。第 $j$ 个洞最多可以容纳 $c_{j}$ 只老鼠，因此不能有超过 $c_{j}$ 只老鼠进入该洞。 请问所有老鼠都能藏进洞里所需通过的最小距离和是多少？如果第 $i$ 只老鼠跑进了第 $j$ 个洞，则它需要走的距离为 $|x_{i}-p_{j}|$。 请输出所需的最小距离和。

第一行包含两个整数 $n$，$m$（$1 \leq n, m \leq 5000$）——表示老鼠的数量和洞的数量。 第二行包含 $n$ 个整数 $x_{1},x_{2},...,x_{n}$（$-10^9 \leq x_{i} \leq 10^9$），表示每只老鼠的位置。 接下来 $m$ 行，每行包含两个整数 $p_{j},c_{j}$（$-10^9 \leq p_{j} \leq 10^9, 1 \leq c_{j} \leq 5000$），表示第 $j$ 个洞的位置和其最大容量。

输出一个整数，表示最小距离和。如果无解，则输出 -1。

由 ChatGPT 5 翻译