#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline long long read1() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 1e6 + 10;
using namespace std;
int n, h, r, c;
int i, j, k, x, y;
int f[2][N], s[N], *F = f[0], *G = f[1];
pair<int, int> V[N];
inline void minn(int &x, const int y) { x > y ? x = y : 0; }
int main() {
  n = read();
  k = read();
  h = min(n, (int)sqrt(6 * k));
  for (int i = 0; i < (k); i++) {
    int r = read();
    int c = read();
    x = n - r + c;
    y = n - r + 1;
    V[i] = make_pair(x, y);
  }
  sort(V, V + k);
  memset(f, 127, sizeof f);
  F[0] = x = 0;
  for (int i = 1; i <= n; i++) {
    y = min(i, h);
    memset(G, 127, y + 2 << 2);
    memset(s, 0, y + 2 << 2);
    for (; x < k && V[x].first == i; x++)
      s[V[x].second > y ? y + 1 : V[x].second]++;
    for (int j = y; j >= 0; j--) s[j] += s[j + 1];
    G[0] = F[0] + s[1] * 3;
    for (int j = 1; j <= y; j++)
      minn(G[0], F[j - 1] + (j * (j + 1) >> 1) + 2 + s[j + 1] * 3);
    for (int j = 1; j <= y; j++) {
      G[j] = G[j - 1];
      minn(G[j], F[j - 1] + s[j + 1] * 3);
    }
    swap(F, G);
  }
  printf("%d\n", F[0]);
  return 0;
}
