#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma optimize("fast-math")
using namespace std;
int mux(int a, int b) {
  if (a > b) return a;
  return b;
}
int mun(int a, int b) {
  if (a < b) return a;
  return b;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename U>
ostream &operator<<(ostream &o, pair<T, U> p) {
  o << p.first << " " << p.second << endl;
  return o;
}
template <typename T>
istream &operator>>(istream &o, vector<T> &arr) {
  for (int i = 0; i < arr.size(); i++) o >> arr[i];
  return o;
}
template <typename T>
ostream &operator<<(ostream &o, vector<T> &arr) {
  for (int i = 0; i < arr.size(); i++) o << arr[i] << " ";
  o << endl;
  return o;
}
inline long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcdex(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long xx, yy;
  long long gc = gcdex(b, a % b, yy, xx);
  x = xx;
  y = yy - (a / b) * xx;
  return gc;
}
inline long long pwm(long long xx, long long pow, long long MD) {
  if (pow < 0) {
    pow = pow % (MD - 1) + MD - 1;
  }
  long long mlt = 1;
  while (pow) {
    if (pow & 1) {
      mlt *= xx;
      mlt %= MD;
    }
    xx *= xx;
    pow >>= 1;
    xx %= MD;
  }
  return mlt;
}
inline int inv(long long r, int _mod) { return pwm(r % _mod, _mod - 2, _mod); }
inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
  if (pow == 0) {
    return 0;
  }
  int hpow = 1 << (pow - 1);
  int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  seg = (seg + rotate) & 3;
  const int rotateDelta[4] = {3, 0, 0, 1};
  int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  int nrot = (rotate + rotateDelta[seg]) & 3;
  int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
  int64_t ans = seg * subSquareSize;
  int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
  ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  return ans;
}
const int mxn = 5e3 + 5;
pair<long long, long long> nor[mxn];
long long x[mxn];
long long dp2[2][mxn];
long long dist[mxn][mxn];
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n + 1; i++) {
    cin >> x[i];
  }
  int alll = 0;
  for (int i = 1; i < m + 1; i++) {
    cin >> nor[i].first;
    cin >> nor[i].second;
    alll += nor[i].second;
  }
  if (n > alll) {
    cout << -1 << endl;
    return;
  }
  sort(x + 1, x + n + 1);
  sort(nor + 1, nor + m + 1);
  for (int i = 1; i < m + 1; i++) {
    for (int j = 1; j < n + 1; j++) {
      dist[i][j] = dist[i][j - 1] + abs(x[j] - nor[i].first);
    }
  }
  for (int i = 1; i < n + 1; i++) {
    if (i > nor[1].second)
      dp2[0][i] = 1e14;
    else
      dp2[0][i] = dist[1][i];
  }
  cout << endl;
  for (int i = 2; i < m + 1; i++) {
    stack<pair<long long, long long>> s1, s2;
    long long new_element = 0;
    long long minima =
        s1.empty() ? new_element : min(new_element, s1.top().second);
    s1.push(make_pair(new_element, minima));
    for (int j = 1, l = -nor[i].second; j < n + 1; j++, l++) {
      long long new_element = dp2[0][j] - dist[i][j];
      long long minima =
          s1.empty() ? new_element : min(new_element, s1.top().second);
      s1.push(make_pair(new_element, minima));
      if (l >= 0) {
        if (s2.empty())
          while (!s1.empty()) {
            long long element = s1.top().first;
            s1.pop();
            long long minima =
                s2.empty() ? element : min(element, s2.top().second);
            s2.push(make_pair(element, minima));
          }
        int result = s2.top().first;
        s2.pop();
      }
      long long kek;
      if (s1.empty() || s2.empty())
        kek = s1.empty() ? s2.top().second : s1.top().second;
      else
        kek = min(s1.top().second, s2.top().second);
      dp2[1][j] = dist[i][j] + kek;
      if ((j >= (nor[i].second + 1) && i == 1)) {
        dp2[1][j] = 1e14;
      }
    }
    for (int j = 0; j < n + 1; j++) {
      dp2[0][j] = dp2[1][j];
    }
  }
  cout << dp2[0][n];
}
void testcases(int n) {
  n = 1 - n;
  if (!n) cin >> n;
  for (int i = 0; i < n; i++) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  unsigned int beg_time = clock();
  testcases(0);
  unsigned int end_time = clock();
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#pragma GCC optimize("O3", "unroll-loops")
#pragma optimize("fast-math")
using namespace std;
int mux(int a, int b) {
  if (a > b) return a;
  return b;
}
int mun(int a, int b) {
  if (a < b) return a;
  return b;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename U>
ostream &operator<<(ostream &o, pair<T, U> p) {
  o << p.first << " " << p.second << endl;
  return o;
}
template <typename T>
istream &operator>>(istream &o, vector<T> &arr) {
  for (int i = 0; i < arr.size(); i++) o >> arr[i];
  return o;
}
template <typename T>
ostream &operator<<(ostream &o, vector<T> &arr) {
  for (int i = 0; i < arr.size(); i++) o << arr[i] << " ";
  o << endl;
  return o;
}
inline long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcdex(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long xx, yy;
  long long gc = gcdex(b, a % b, yy, xx);
  x = xx;
  y = yy - (a / b) * xx;
  return gc;
}
inline long long pwm(long long xx, long long pow, long long MD) {
  if (pow < 0) {
    pow = pow % (MD - 1) + MD - 1;
  }
  long long mlt = 1;
  while (pow) {
    if (pow & 1) {
      mlt *= xx;
      mlt %= MD;
    }
    xx *= xx;
    pow >>= 1;
    xx %= MD;
  }
  return mlt;
}
inline int inv(long long r, int _mod) { return pwm(r % _mod, _mod - 2, _mod); }
inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
  if (pow == 0) {
    return 0;
  }
  int hpow = 1 << (pow - 1);
  int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  seg = (seg + rotate) & 3;
  const int rotateDelta[4] = {3, 0, 0, 1};
  int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  int nrot = (rotate + rotateDelta[seg]) & 3;
  int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
  int64_t ans = seg * subSquareSize;
  int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
  ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  return ans;
}
const int mxn = 5e3 + 5;
pair<long long, long long> nor[mxn];
long long x[mxn];
long long dp2[2][mxn];
long long dist[mxn][mxn];
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n + 1; i++) {
    cin >> x[i];
  }
  int alll = 0;
  for (int i = 1; i < m + 1; i++) {
    cin >> nor[i].first;
    cin >> nor[i].second;
    alll += nor[i].second;
  }
  if (n > alll) {
    cout << -1 << endl;
    return;
  }
  sort(x + 1, x + n + 1);
  sort(nor + 1, nor + m + 1);
  for (int i = 1; i < m + 1; i++) {
    for (int j = 1; j < n + 1; j++) {
      dist[i][j] = dist[i][j - 1] + abs(x[j] - nor[i].first);
    }
  }
  for (int i = 1; i < n + 1; i++) {
    if (i > nor[1].second)
      dp2[0][i] = 1e14;
    else
      dp2[0][i] = dist[1][i];
  }
  cout << endl;
  for (int i = 2; i < m + 1; i++) {
    stack<pair<long long, long long>> s1, s2;
    long long new_element = 0;
    long long minima =
        s1.empty() ? new_element : min(new_element, s1.top().second);
    s1.push(make_pair(new_element, minima));
    for (int j = 1, l = -nor[i].second; j < n + 1; j++, l++) {
      long long new_element = dp2[0][j] - dist[i][j];
      long long minima =
          s1.empty() ? new_element : min(new_element, s1.top().second);
      s1.push(make_pair(new_element, minima));
      if (l >= 0) {
        if (s2.empty())
          while (!s1.empty()) {
            long long element = s1.top().first;
            s1.pop();
            long long minima =
                s2.empty() ? element : min(element, s2.top().second);
            s2.push(make_pair(element, minima));
          }
        int result = s2.top().first;
        s2.pop();
      }
      long long kek;
      if (s1.empty() || s2.empty())
        kek = s1.empty() ? s2.top().second : s1.top().second;
      else
        kek = min(s1.top().second, s2.top().second);
      dp2[1][j] = dist[i][j] + kek;
      if ((j >= (nor[i].second + 1) && i == 1)) {
        dp2[1][j] = 1e14;
      }
    }
    for (int j = 0; j < n + 1; j++) {
      dp2[0][j] = dp2[1][j];
    }
  }
  cout << dp2[0][n];
}
void testcases(int n) {
  n = 1 - n;
  if (!n) cin >> n;
  for (int i = 0; i < n; i++) {
    solve();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  unsigned int beg_time = clock();
  testcases(0);
  unsigned int end_time = clock();
  return 0;
}

```