老鼠与洞穴

• 时间限制：1.5 秒
• 内存限制：256 MiB

题目描述

一条走廊可以看作数轴。数轴上有 $n$ 只老鼠和 $m$ 个洞：第 $i$ 只老鼠位于坐标 $x_i$；第 $j$ 个洞位于坐标 $p_j$，最多能容纳 $c_j$ 只老鼠。

每只老鼠必须进入一个洞，且进入同一洞的老鼠数量不能超过该洞容量。老鼠从 $x_i$ 前往 $p_j$ 的移动距离为 $|x_i-p_j|$。

求所有老鼠进入洞穴所需的最小总移动距离。如果无法容纳所有老鼠，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$，分别表示老鼠和洞穴的数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示各只老鼠的位置。

接下来 $m$ 行，每行包含两个整数 $p_j,c_j$，表示一个洞的位置和容量。

输出格式

输出最小总移动距离；如果无解，输出 $-1$。

样例输入 1

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

样例输出 1

11

样例输入 2

7 2
10 20 30 40 50 45 35
-1000000000 10
1000000000 1

样例输出 2

7000000130

数据范围

$1\le n,m\le5000$，$-10^9\le x_i,p_j\le10^9$，$1\le c_j\le5000$。