# CF797F Mice and Holes

• 30通过
• 69提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 省选/NOI-
• 时空限制 1500ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

n个老鼠，m个洞，告诉你他们的一维坐标和m个洞的容量限制，问最小总距离。

## 题目描述

One day Masha came home and noticed $n$ mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor.

The corridor can be represeted as a numeric axis with $n$ mice and $m$ holes on it. $i$ th mouse is at the coordinate $x_{i}$ , and $j$ th hole — at coordinate $p_{j}$ . $j$ th hole has enough room for $c_{j}$ mice, so not more than $c_{j}$ mice can enter this hole.

What is the minimum sum of distances that mice have to go through so that they all can hide in the holes? If $i$ th mouse goes to the hole $j$ , then its distance is $|x_{i}-p_{j}|$ .

Print the minimum sum of distances.

## 输入输出格式

输入格式：

The first line contains two integer numbers $n$ , $m$ ( $1<=n,m<=5000$ ) — the number of mice and the number of holes, respectively.

The second line contains $n$ integers $x_{1},x_{2},...,x_{n}$ ( $-10^{9}<=x_{i}<=10^{9}$ ), where $x_{i}$ is the coordinate of $i$ th mouse.

Next $m$ lines contain pairs of integer numbers $p_{j},c_{j}$ ( $-10^{9}<=p_{j}<=10^{9},1<=c_{j}<=5000$ ), where $p_{j}$ is the coordinate of $j$ th hole, and $c_{j}$ is the maximum number of mice that can hide in the hole $j$ .

输出格式：

Print one integer number — the minimum sum of distances. If there is no solution, print -1 instead.

## 输入输出样例

输入样例#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

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。