Educational Codeforces Round 19 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

greedy

sortings

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Mice and Holes

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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.

Input

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*.

Output

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

Examples

Input

4 5

6 2 8 9

3 6

2 1

3 6

4 7

4 7

Output

11

Input

7 2

10 20 30 40 50 45 35

-1000000000 10

1000000000 1

Output

7000000130

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/05/2023 09:20:39 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|