← 返回题目列表

Codeforces · 797/F

F. 老鼠和洞

中文机器翻译题面 查看原题

有一天,玛莎回到家,发现她公寓的走廊里有n只老鼠。当然,她大声喊叫,吓得老鼠开始往走廊的洞里跑。

走廊可以被表示为一个数字轴,上面有 n 个老鼠和 m 个孔。第 i 个鼠标位于坐标 xi 处,第 j 个孔位于坐标 pj 处。第 j 个孔有足够的空间容纳 cj 小鼠,因此不能超过 cj 小鼠进入该孔。

老鼠必须经过多少距离才能全部躲进洞里?如果第i只老鼠进入洞j,那么它的距离是|xi - pj|。

打印最小距离总和。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 5000) — 分别是老鼠的数量和洞的数量。

第二行包含 n 个整数 x1, x2, ..., xn ( - 109 ≤ xi ≤ 109),其中 xi 是第 i 个鼠标的坐标。

接下来 m 行包含整数对 pj, cj ( - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000),其中 pj 是第 j 个洞的坐标,cj 是 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