Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

F. Mice and Holes
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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. ith mouse is at the coordinate x i, and jth hole — at coordinate p j. jth 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 ith 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 ( - 109 ≤ x i ≤ 109), where x i is the coordinate of ith mouse.

Next m lines contain pairs of integer numbers p j, c j ( - 109 ≤ p j ≤ 109, 1 ≤ c j ≤ 5000), where p j is the coordinate of jth 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 56 2 8 93 62 13 64 74 7
Output
11
Input
7 210 20 30 40 50 45 35-1000000000 101000000000 1
Output
7000000130