有一天,玛莎回到家,发现她公寓的走廊里有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