#include <bits/stdc++.h>
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = obuf + SIZE - 1;
char _st[55];
int _qr = 0;
inline char gc() {
  return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template <class T1, class... T2>
inline void qread(T1 &IEE, T2 &...ls) {
  register T1 __ = 0, ___ = 1;
  register char ch;
  while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
  do {
    __ = (__ << 1) + (__ << 3) + (ch ^ 48);
  } while (isdigit(ch = gc()));
  __ *= ___;
  IEE = __;
  qread(ls...);
  return;
}
template <class T>
inline void QreadArr(T Begin, T End) {
  while (Begin != End) {
    qread(*Begin);
    ++Begin;
  }
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
  return;
}
inline void putc_(char _x) {
  *oS++ = _x;
  if (oS == oT) flush();
}
inline void qwrite() {}
template <class T1, class... T2>
inline void qwrite(T1 IEE, T2... ls) {
  if (!IEE) putc_('0');
  if (IEE < 0) putc_('-'), IEE = -IEE;
  while (IEE) _st[++_qr] = IEE % 10 + '0', IEE /= 10;
  while (_qr) putc_(_st[_qr--]);
  qwrite(ls...);
  return;
}
template <class T>
inline void WriteArr(T Begin, T End) {
  const char Kg = ' ', Edl = '\n';
  while (Begin != End) {
    qwrite(*Begin);
    ++Begin;
    putc_(Kg);
  }
  putc_(Edl);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher;
}  // namespace IO
using namespace IO;
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
long long My_Rand(long long Mod) { return (unsigned long long)(rnd()) % Mod; }
template <class T1, class T2>
T1 Min(const T1 x, const T2 y) {
  return x > y ? y : x;
}
template <class T1, class T2>
T1 Max(const T1 x, const T2 y) {
  return x > y ? x : y;
}
template <class T1, class T2>
void To_max(T1 &x, const T2 y) {
  x < y ? x = y : x = x;
}
template <class T1, class T2>
void To_min(T1 &x, const T2 y) {
  x > y ? x = y : x = x;
}
inline long long qpow(long long n, long long base, long long mod = 1e18) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = ret * base % mod;
    base = base * base % mod;
    n >>= 1;
  }
  return ret % mod;
}
inline long long gcd(long long x, long long y) {
  return !y ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }
const int N = 5005;
const long long inf = 1e18;
struct Node {
  int pos;
  int c;
  bool operator<(const Node &oth) const { return pos < oth.pos; }
} h[N];
int n, m, sum, hd, tl;
int a[N], q[N];
long long s[N], v[N], dp[N][N];
int main() {
  qread(n, m);
  QreadArr(a + 1, a + n + 1);
  for (int i = 1; i <= m; ++i) qread(h[i].pos, h[i].c);
  sort(a + 1, a + n + 1);
  sort(h + 1, h + m + 1);
  for (int i = 1; i <= n; ++i) dp[0][i] = inf;
  for (int i = 1; i <= m; ++i) {
    sum += h[i].c;
    for (int j = 1; j <= n; ++j) s[j] = abs(h[i].pos - a[j]) + s[j - 1];
    hd = 1, tl = 0;
    for (int j = 0; j <= n; ++j) {
      while (hd <= tl && q[hd] < j - h[i].c) ++hd;
      while (hd <= tl && dp[i - 1][j] - s[j] <= v[tl]) --tl;
      q[++tl] = j;
      v[tl] = dp[i - 1][j] - s[j];
      if (sum >= j)
        dp[i][j] = s[j] + v[hd];
      else
        dp[i][j] = inf;
    }
  }
  printf("%lld\n", dp[m][n] == inf ? -1 : dp[m][n]);
  return 0;
}

### Prompt

Please formulate a cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = obuf + SIZE - 1;
char _st[55];
int _qr = 0;
inline char gc() {
  return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template <class T1, class... T2>
inline void qread(T1 &IEE, T2 &...ls) {
  register T1 __ = 0, ___ = 1;
  register char ch;
  while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
  do {
    __ = (__ << 1) + (__ << 3) + (ch ^ 48);
  } while (isdigit(ch = gc()));
  __ *= ___;
  IEE = __;
  qread(ls...);
  return;
}
template <class T>
inline void QreadArr(T Begin, T End) {
  while (Begin != End) {
    qread(*Begin);
    ++Begin;
  }
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
  return;
}
inline void putc_(char _x) {
  *oS++ = _x;
  if (oS == oT) flush();
}
inline void qwrite() {}
template <class T1, class... T2>
inline void qwrite(T1 IEE, T2... ls) {
  if (!IEE) putc_('0');
  if (IEE < 0) putc_('-'), IEE = -IEE;
  while (IEE) _st[++_qr] = IEE % 10 + '0', IEE /= 10;
  while (_qr) putc_(_st[_qr--]);
  qwrite(ls...);
  return;
}
template <class T>
inline void WriteArr(T Begin, T End) {
  const char Kg = ' ', Edl = '\n';
  while (Begin != End) {
    qwrite(*Begin);
    ++Begin;
    putc_(Kg);
  }
  putc_(Edl);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher;
}  // namespace IO
using namespace IO;
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
long long My_Rand(long long Mod) { return (unsigned long long)(rnd()) % Mod; }
template <class T1, class T2>
T1 Min(const T1 x, const T2 y) {
  return x > y ? y : x;
}
template <class T1, class T2>
T1 Max(const T1 x, const T2 y) {
  return x > y ? x : y;
}
template <class T1, class T2>
void To_max(T1 &x, const T2 y) {
  x < y ? x = y : x = x;
}
template <class T1, class T2>
void To_min(T1 &x, const T2 y) {
  x > y ? x = y : x = x;
}
inline long long qpow(long long n, long long base, long long mod = 1e18) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = ret * base % mod;
    base = base * base % mod;
    n >>= 1;
  }
  return ret % mod;
}
inline long long gcd(long long x, long long y) {
  return !y ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }
const int N = 5005;
const long long inf = 1e18;
struct Node {
  int pos;
  int c;
  bool operator<(const Node &oth) const { return pos < oth.pos; }
} h[N];
int n, m, sum, hd, tl;
int a[N], q[N];
long long s[N], v[N], dp[N][N];
int main() {
  qread(n, m);
  QreadArr(a + 1, a + n + 1);
  for (int i = 1; i <= m; ++i) qread(h[i].pos, h[i].c);
  sort(a + 1, a + n + 1);
  sort(h + 1, h + m + 1);
  for (int i = 1; i <= n; ++i) dp[0][i] = inf;
  for (int i = 1; i <= m; ++i) {
    sum += h[i].c;
    for (int j = 1; j <= n; ++j) s[j] = abs(h[i].pos - a[j]) + s[j - 1];
    hd = 1, tl = 0;
    for (int j = 0; j <= n; ++j) {
      while (hd <= tl && q[hd] < j - h[i].c) ++hd;
      while (hd <= tl && dp[i - 1][j] - s[j] <= v[tl]) --tl;
      q[++tl] = j;
      v[tl] = dp[i - 1][j] - s[j];
      if (sum >= j)
        dp[i][j] = s[j] + v[hd];
      else
        dp[i][j] = inf;
    }
  }
  printf("%lld\n", dp[m][n] == inf ? -1 : dp[m][n]);
  return 0;
}

```