Problem: 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 xi, and jth hole — at coordinate pj. jth hole has enough room for cj mice, so not more than cj 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 |xi - pj|.

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 x1, x2, ..., xn ( - 109 ≤ xi ≤ 109), where xi is the coordinate of ith mouse.

Next m lines contain pairs of integer numbers pj, cj ( - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000), where pj is the coordinate of jth hole, and cj 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
class Scanner {
  char cht;
  bool ifNegative;
  char stringBuf[10000];
  char nc() {
    static char buf[524288];
    static char *p1 = buf + 524288, *pend = buf + 524288;
    if (p1 == pend) {
      p1 = buf;
      pend = buf + fread(buf, 1, 524288, stdin);
      if (pend == p1) return ' ';
    }
    if (*p1 == '-') {
      ifNegative = true;
      p1++;
      return nc();
    }
    return *p1++;
  }
  inline bool blank(char ch) {
    return ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t';
  }

 public:
  Scanner operator>>(int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(long long int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(string &str) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (stringBuf[p++] = cht; !blank(cht = nc()); stringBuf[p++] = cht)
      ;
    stringBuf[p] = '\0';
    str = stringBuf;
    return *this;
  }
  Scanner operator>>(char str[]) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (str[p++] = cht; !blank(cht = nc()); str[p++] = cht)
      ;
    str[p] = '\0';
    return *this;
  }
  template <typename F>
  inline Scanner operator>>(F &f) {
    cin >> f;
    return *this;
  }
};
class Printer {
  int num;
  char chr[21];

 public:
  Printer operator<<(int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  Printer operator<<(long long int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  inline Printer operator<<(char x) {
    putchar(x);
    return *this;
  }
  Printer operator<<(const char str[]) {
    int p = 0;
    while (str[p] != '\0') {
      putchar(str[p++]);
    }
    return *this;
  }
  inline Printer operator<<(string &x) {
    for (string::iterator i = x.begin(); i < x.end(); i++) putchar(*i);
    return *this;
  }
  template <typename F>
  inline Printer operator<<(F &f) {
    cout << f;
    return *this;
  }
};
Scanner qin;
Printer qout;
}  // namespace FastIO
using namespace FastIO;
const int MAXN = 100005;
const int MAXM = 355;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double PI = 3.141593;
const double E = 2.718282;
const double PHI = 1.618034;
int n, m, cnt;
int mi[MAXN], ho[MAXN][2];
int ti[MAXN][2], dp[MAXN * 3][2];
long long sum, tag1, tag2, dp0;
stack<long long> dp1, dp2;
struct stg {
  int a, b;
  bool operator<(const stg t) const { return a < t.a; }
} now[MAXN];
int main() {
  qin >> n >> m;
  for (register long long i = 1; i <= n; i++) qin >> mi[i];
  sort(mi + 1, mi + n + 1);
  for (register long long i = 1; i <= m; i++) {
    qin >> now[i].a >> now[i].b;
    sum += now[i].b;
  }
  sort(now + 1, now + m + 1);
  for (register long long i = 1; i <= m; i++) {
    ho[i][0] = now[i].a;
    ho[i][1] = now[i].b;
  }
  if (sum < n) {
    puts("-1");
    return 0;
  }
  int p1 = 1, p2 = 1;
  while (p1 <= n || p2 <= m) {
    if (p1 <= n && (p2 > m || ho[p2][0] > mi[p1])) {
      ++p1;
      if (!dp1.empty()) {
        int t = dp1.top();
        dp1.pop();
        if (++ti[t][0] != ho[t][1]) dp1.push(t);
      } else
        ++cnt;
    } else if (cnt < ho[p2][1]) {
      ti[p2][0] = cnt;
      cnt = 0;
      dp1.push(p2++);
    } else {
      ti[p2][0] = ho[p2][1];
      cnt -= ho[p2++][1];
    }
  }
  p1 = n;
  p2 = m;
  cnt = 0;
  dp1 = dp2;
  while (p1 || p2) {
    if (p1 && (!p2 || ho[p2][0] < mi[p1])) {
      --p1;
      if (!dp1.empty()) {
        int t = dp1.top();
        dp1.pop();
        if (++ti[t][1] != ho[t][1]) dp1.push(t);
      } else
        ++cnt;
    } else if (cnt < ho[p2][1]) {
      ti[p2][1] = cnt;
      cnt = 0;
      dp1.push(p2--);
    } else {
      ti[p2][1] = ho[p2][1];
      cnt -= ho[p2--][1];
    }
  }
  p1 = 1;
  p2 = 1;
  cnt = 0;
  while (p1 <= n || p2 <= m) {
    if (p1 <= n && (p2 > m || ho[p2][0] > mi[p1]))
      dp[++cnt][0] = mi[p1++];
    else {
      for (int i = min(ti[p2][0] + ti[p2][1], ho[p2][1]); i; --i) {
        dp[++cnt][0] = ho[p2][0];
        dp[cnt][1] = 1;
        --ti[p2][0];
      }
      ++p2;
    }
  }
  dp1 = dp2;
  for (register long long i = 1; i <= cnt; i++) {
    if (!dp[i][1]) {
      dp1.push(dp0 - tag1);
      tag1 -= dp[i][0];
      tag2 += dp[i][0];
      if (!dp2.empty()) {
        dp0 = dp2.top() + tag2;
        dp2.pop();
      } else
        dp0 = 1e15;
    } else {
      dp2.push(dp0 - tag2);
      tag1 += dp[i][0];
      tag2 -= dp[i][0];
      if (!dp1.empty()) {
        dp0 = min(dp0, dp1.top() + tag1);
        dp1.pop();
      }
    }
  }
  cout << dp0;
  return 0;
}