#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC target("avx,tune=native")
using namespace std;
class CodeHash {
 public:
  string precise(double number, int prec) {
    stringstream ss;
    ss << fixed << setprecision(prec) << number;
    return ss.str();
  }
};
class ScanReader {
 private:
  FILE *stream;
  char buffer[1 << 11];
  bool is_digit[1 << 8];
  int index, total;
  int scan() {
    if (index >= total) {
      index = 0;
      total = fread(buffer, 1, 1 << 11, stream);
      if (total <= 0) return -1;
    }
    return buffer[index++];
  }
  bool iswhitespace(int n) {
    if (n == ' ' || n == '\n' || n == '\t' || n == '\r' || n == -1) return true;
    return false;
  }

 public:
  ScanReader(FILE *stream) {
    this->stream = stream;
    index = total = 0;
    for (int i = 0; i < 1 << 8; i++) is_digit[i] = isdigit(i);
  }
  int scanInt() {
    int integer = 0, temp = scan();
    while (iswhitespace(temp)) temp = scan();
    int neg = 1;
    if (temp == '-') neg *= -1, temp = scan();
    while (!iswhitespace(temp))
      if (is_digit[temp]) integer *= 10, integer += (temp - '0'), temp = scan();
    return neg * integer;
  }
  long long scanLong() {
    long long integer = 0;
    int temp = scan();
    while (iswhitespace(temp)) temp = scan();
    int neg = 1;
    if (temp == '-') neg *= -1, temp = scan();
    while (!iswhitespace(temp))
      if (is_digit[temp]) integer *= 10, integer += (temp - '0'), temp = scan();
    return neg * integer;
  }
  string scanString() {
    string ss = "";
    int temp = scan();
    while (iswhitespace(temp)) temp = scan();
    while (!iswhitespace(temp)) ss += temp, temp = scan();
    return ss;
  }
  double scanDouble() {
    int c = scan();
    while (iswhitespace(c)) c = scan();
    int sgn = 1;
    if (c == '-') sgn = -1, c = scan();
    double res = 0;
    while (!iswhitespace(c) && c != '.') {
      if (c == 'e' || c == 'E') return res * pow(10, scanInt());
      res *= 10;
      res += c - '0';
      c = scan();
    }
    if (c == '.') {
      c = scan();
      double m = 1;
      while (!iswhitespace(c)) {
        if (c == 'e' || c == 'E') {
          return res * pow(10, scanInt());
        }
        m /= 10;
        res += (c - '0') * m;
        c = scan();
      }
    }
    return res * sgn;
  }
};
class PrintWriter {
 private:
  FILE *stream;
  static const int BUFFER_SIZE = (1 << 11) - 1;
  static const int MAX_OUT_SIZE = 23;
  int size;
  char buffer[BUFFER_SIZE];
  void write(long long v) {
    if (v < 0) buffer[size++] = '-', v *= -1;
    if (v < 10)
      buffer[size++] = v + 48;
    else {
      write(v / 10);
      buffer[size++] = v % 10 + 48;
    }
  }

 public:
  PrintWriter(FILE *stream) {
    this->size = 0;
    this->stream = stream;
  }
  void close() {
    if (size) fwrite(buffer, 1, size, stream);
  }
  void println(long long s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    write(s);
    buffer[size++] = '\n';
  }
  void print(long long s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    write(s);
    buffer[size++] = ' ';
  }
  void println(string s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    for (int i = 0; i < s.length(); i++) {
      buffer[size++] = s[i];
      if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
        fwrite(buffer, 1, size, stream);
        size = 0;
      }
    }
    buffer[size++] = '\n';
  }
  void print(string s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    for (int i = 0; i < s.length(); i++) {
      buffer[size++] = s[i];
      if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
        fwrite(buffer, 1, size, stream);
        size = 0;
      }
    }
  }
};
FILE *fi =
    fopen("C:\\Users\\Nikunj\\CLionProjects\\compe\\testcases\\in.txt", "r+");
FILE *fo =
    fopen("C:\\Users\\Nikunj\\CLionProjects\\compe\\testcases\\out.txt", "w+");
int main() {
  fi = stdin;
  fo = stdout;
  ScanReader *in = new ScanReader(fi);
  PrintWriter *out = new PrintWriter(fo);
  CodeHash *ch = new CodeHash();
  int n = in->scanInt();
  int m = in->scanInt();
  long long *dp = new long long[n + 1];
  int *mouse = new int[n + 1];
  mouse[0] = -1000000001;
  for (int i = 1; i <= n; i++) mouse[i] = in->scanInt();
  int **coordinates = new int *[m + 1];
  coordinates[0] = new int[2];
  coordinates[0][0] = -1000000001;
  for (int i = 1; i <= m; i++) {
    coordinates[i] = new int[2];
    coordinates[i][0] = in->scanInt();
    coordinates[i][1] = in->scanInt();
  }
  auto comp = [](int *u, int *v) { return u[0] < v[0]; };
  sort(mouse, mouse + n + 1);
  sort(coordinates, coordinates + m + 1, comp);
  for (int i = 0; i <= n; i++) dp[i] = 10000000000ll * 5005;
  long long **queue = new long long *[n + 2];
  for (int i = 0; i <= n; i++) queue[i] = new long long[2];
  for (int i = 1; i <= m; i++) {
    for (int i = 0; i <= n; i++) {
      queue[i][0] = 0;
      queue[i][1] = 0;
    }
    int front = 0;
    int back = 0;
    queue[back][0] = 0l;
    queue[back++][1] = 0l;
    long long prev = 0;
    for (int j = 1; j <= n; j++) {
      prev += (abs(mouse[j] - coordinates[i][0]));
      while (front < back && queue[back - 1][0] >= dp[j] - prev) back--;
      queue[back][0] = dp[j] - prev;
      queue[back++][1] = j;
      while (front < back && j - queue[front][1] > coordinates[i][1]) front++;
      dp[j] = min(dp[j], queue[front][0] + prev);
    }
  }
  if (dp[n] == 10000000000l * 5005)
    out->println(-1);
  else
    out->println(dp[n]);
  out->close();
  return 0;
}

### Prompt

Generate 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>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC target("avx,tune=native")
using namespace std;
class CodeHash {
 public:
  string precise(double number, int prec) {
    stringstream ss;
    ss << fixed << setprecision(prec) << number;
    return ss.str();
  }
};
class ScanReader {
 private:
  FILE *stream;
  char buffer[1 << 11];
  bool is_digit[1 << 8];
  int index, total;
  int scan() {
    if (index >= total) {
      index = 0;
      total = fread(buffer, 1, 1 << 11, stream);
      if (total <= 0) return -1;
    }
    return buffer[index++];
  }
  bool iswhitespace(int n) {
    if (n == ' ' || n == '\n' || n == '\t' || n == '\r' || n == -1) return true;
    return false;
  }

 public:
  ScanReader(FILE *stream) {
    this->stream = stream;
    index = total = 0;
    for (int i = 0; i < 1 << 8; i++) is_digit[i] = isdigit(i);
  }
  int scanInt() {
    int integer = 0, temp = scan();
    while (iswhitespace(temp)) temp = scan();
    int neg = 1;
    if (temp == '-') neg *= -1, temp = scan();
    while (!iswhitespace(temp))
      if (is_digit[temp]) integer *= 10, integer += (temp - '0'), temp = scan();
    return neg * integer;
  }
  long long scanLong() {
    long long integer = 0;
    int temp = scan();
    while (iswhitespace(temp)) temp = scan();
    int neg = 1;
    if (temp == '-') neg *= -1, temp = scan();
    while (!iswhitespace(temp))
      if (is_digit[temp]) integer *= 10, integer += (temp - '0'), temp = scan();
    return neg * integer;
  }
  string scanString() {
    string ss = "";
    int temp = scan();
    while (iswhitespace(temp)) temp = scan();
    while (!iswhitespace(temp)) ss += temp, temp = scan();
    return ss;
  }
  double scanDouble() {
    int c = scan();
    while (iswhitespace(c)) c = scan();
    int sgn = 1;
    if (c == '-') sgn = -1, c = scan();
    double res = 0;
    while (!iswhitespace(c) && c != '.') {
      if (c == 'e' || c == 'E') return res * pow(10, scanInt());
      res *= 10;
      res += c - '0';
      c = scan();
    }
    if (c == '.') {
      c = scan();
      double m = 1;
      while (!iswhitespace(c)) {
        if (c == 'e' || c == 'E') {
          return res * pow(10, scanInt());
        }
        m /= 10;
        res += (c - '0') * m;
        c = scan();
      }
    }
    return res * sgn;
  }
};
class PrintWriter {
 private:
  FILE *stream;
  static const int BUFFER_SIZE = (1 << 11) - 1;
  static const int MAX_OUT_SIZE = 23;
  int size;
  char buffer[BUFFER_SIZE];
  void write(long long v) {
    if (v < 0) buffer[size++] = '-', v *= -1;
    if (v < 10)
      buffer[size++] = v + 48;
    else {
      write(v / 10);
      buffer[size++] = v % 10 + 48;
    }
  }

 public:
  PrintWriter(FILE *stream) {
    this->size = 0;
    this->stream = stream;
  }
  void close() {
    if (size) fwrite(buffer, 1, size, stream);
  }
  void println(long long s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    write(s);
    buffer[size++] = '\n';
  }
  void print(long long s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    write(s);
    buffer[size++] = ' ';
  }
  void println(string s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    for (int i = 0; i < s.length(); i++) {
      buffer[size++] = s[i];
      if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
        fwrite(buffer, 1, size, stream);
        size = 0;
      }
    }
    buffer[size++] = '\n';
  }
  void print(string s) {
    if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
      fwrite(buffer, 1, size, stream);
      size = 0;
    }
    for (int i = 0; i < s.length(); i++) {
      buffer[size++] = s[i];
      if ((size ^ BUFFER_SIZE) < MAX_OUT_SIZE) {
        fwrite(buffer, 1, size, stream);
        size = 0;
      }
    }
  }
};
FILE *fi =
    fopen("C:\\Users\\Nikunj\\CLionProjects\\compe\\testcases\\in.txt", "r+");
FILE *fo =
    fopen("C:\\Users\\Nikunj\\CLionProjects\\compe\\testcases\\out.txt", "w+");
int main() {
  fi = stdin;
  fo = stdout;
  ScanReader *in = new ScanReader(fi);
  PrintWriter *out = new PrintWriter(fo);
  CodeHash *ch = new CodeHash();
  int n = in->scanInt();
  int m = in->scanInt();
  long long *dp = new long long[n + 1];
  int *mouse = new int[n + 1];
  mouse[0] = -1000000001;
  for (int i = 1; i <= n; i++) mouse[i] = in->scanInt();
  int **coordinates = new int *[m + 1];
  coordinates[0] = new int[2];
  coordinates[0][0] = -1000000001;
  for (int i = 1; i <= m; i++) {
    coordinates[i] = new int[2];
    coordinates[i][0] = in->scanInt();
    coordinates[i][1] = in->scanInt();
  }
  auto comp = [](int *u, int *v) { return u[0] < v[0]; };
  sort(mouse, mouse + n + 1);
  sort(coordinates, coordinates + m + 1, comp);
  for (int i = 0; i <= n; i++) dp[i] = 10000000000ll * 5005;
  long long **queue = new long long *[n + 2];
  for (int i = 0; i <= n; i++) queue[i] = new long long[2];
  for (int i = 1; i <= m; i++) {
    for (int i = 0; i <= n; i++) {
      queue[i][0] = 0;
      queue[i][1] = 0;
    }
    int front = 0;
    int back = 0;
    queue[back][0] = 0l;
    queue[back++][1] = 0l;
    long long prev = 0;
    for (int j = 1; j <= n; j++) {
      prev += (abs(mouse[j] - coordinates[i][0]));
      while (front < back && queue[back - 1][0] >= dp[j] - prev) back--;
      queue[back][0] = dp[j] - prev;
      queue[back++][1] = j;
      while (front < back && j - queue[front][1] > coordinates[i][1]) front++;
      dp[j] = min(dp[j], queue[front][0] + prev);
    }
  }
  if (dp[n] == 10000000000l * 5005)
    out->println(-1);
  else
    out->println(dp[n]);
  out->close();
  return 0;
}

```