题目描述

一天，玛莎回到家，发现公寓走廊里有 $n$ 只老鼠。她大声呵斥，吓得老鼠开始向走廊上的洞跑去。

走廊可以表示为一个有 $n$ 只老鼠和 $m$ 个洞的数轴，第 $i$ 只老鼠位于坐标 $x_i$，第 $j$ 个洞位于坐标 $p_j$。第 $j$ 个洞有足够的空间容纳 $c_{j}$ 只老鼠，因此不能超过 $c_{j}$ 只老鼠进入该洞。

老鼠要躲进洞里，必须经过的最小距离之和是多少？如果第 $i$ 只老鼠到达第 $j$ 个洞，则其距离为 $| x_{i}-p_{j} |$。

输出最小距离和。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 5000$。

第二行 $n$ 个整数 $x_i$，$-10^9\le x_i\le 10^9$。

接下来 $m$ 行，每行两个整数 $p_j,c_j$，$-10^9\le p_j\le 10^9$，$1\le c_j\le 5000$。

输出格式

输出一个整数表示所有老鼠躲进洞里的最小距离之和，如果无解，输出 $-1$。

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

11

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

7000000130