#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector<int> t[N], f[2], f0[2];
int n, c0[N * 2], lim[N];
void add(int x) {
  for (; x <= n * 2; x += (x & (-x))) c0[x]++;
}
int query(int x) {
  int ret = 0;
  for (; x; x -= (x & (-x))) ret += c0[x];
  return ret;
}
void up(int &a, int b) {
  if (a == -1 || a > b) a = b;
}
int main() {
  int k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; i++) {
    int r, c, x, y;
    scanf("%d%d", &r, &c);
    t[c].push_back(n - r + 1);
  }
  for (int i = n; i; i--)
    if (t[i].size()) {
      sort(t[i].begin(), t[i].end());
      for (int j = 0; j <= t[i].size() - 1; j++) add(i + t[i][j]);
      for (int j = t[i].size() - 1; j >= 0; j--)
        if (t[i][j] * (t[i][j] + 1) / 2 + 2 <= query(i + t[i][j]) * 3) {
          lim[i] = t[i][j];
          break;
        }
      if (lim[i + 1] + 1 > lim[i] &&
          (lim[i + 1] + 1) * (lim[i + 1] + 2) / 2 + 2 <=
              query(i + lim[i + 1] + 1) * 3)
        lim[i] = lim[i + 1] + 1;
    }
  for (int i = 1; i <= n; i++) {
    lim[i] = max(lim[i], lim[i - 1] - 1);
    lim[i] = min(800, n - i + 1);
  }
  f[0].resize(800 + 1, 1e9);
  f0[0].resize(800 + 1, 1e9);
  f[1].resize(800 + 1, 1e9);
  f0[1].resize(800 + 1, 1e9);
  f0[0][0] = 0;
  for (int i = 0; i <= n; i++) {
    int cnt = t[i].size(), ll = 0;
    int i0 = i & 1, i1 = (i + 1) & 1;
    for (int j = 0; j <= lim[i]; j++) {
      if (ll <= (int)t[i].size() - 1 && j == t[i][ll]) cnt--, ll++;
      if (j < lim[i]) {
        up(f[i0][j + 1], f[i0][j] + j + 1);
        up(f[i0][j + 1], f0[i0][j] + (j + 1) * (j + 2) / 2 + 2);
      }
      if (j) {
        up(f0[i1][j - 1], f0[i0][j] + cnt * 3);
        up(f0[i1][j - 1], f[i0][j] + cnt * 3);
      } else {
        up(f0[i1][j], f0[i0][j] + cnt * 3);
        up(f0[i1][j], f[i0][j] + cnt * 3);
      }
      f[i0][j] = f0[i0][j] = 1e9;
    }
  }
  printf("%d\n", f0[(n + 1) & 1][0]);
  return 0;
}
