A10910 | Mice and Holes

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.