#include <bits/stdc++.h>
using namespace std;
int n, m, ff[800], lim, f[2][800], g[101000];
struct rec {
  int x, y;
} a[101000];
bool cmp(rec a, rec b) { return a.x < b.x || a.x == b.x && a.y < b.y; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a[i].y, &a[i].x);
    a[i].y = n - a[i].y + 1;
  }
  sort(a + 1, a + m + 1, cmp);
  ff[0] = 2;
  for (int i = 1; i <= n; i++) {
    ff[i] = ff[i - 1] + i;
    if (ff[i] + i + 1 > m * 3 || i == n) {
      lim = i;
      break;
    }
  }
  ff[0] = 0;
  for (int i = 1; i <= lim; i++) f[0][i] = 1000000000;
  g[0] = 0;
  f[0][0] = 0;
  int z = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= lim; j++) f[i % 2][j] = 1000000000;
    int t = z + 1;
    while (z < m && a[z + 1].x == i) ++z;
    int tt = t;
    for (int j = 0; j < lim; j++) {
      int tot = f[(i - 1) % 2][j + 1];
      if (j == 0) tot = min(tot, f[(i - 1) % 2][0]);
      if (t <= z) {
        while (a[tt].y <= j && tt <= z) ++tt;
        tot += (z - tt + 1) * 3;
      }
      f[i % 2][j] = min(f[i % 2][j], tot);
    }
    tt = t;
    g[i] = 1000000000;
    for (int j = 0; j <= lim; j++) {
      int tot = g[i - 1] + ff[j];
      if (t <= z) {
        while (a[tt].y <= j && tt <= z) ++tt;
        tot += (z - tt + 1) * 3;
      }
      f[i % 2][j] = min(f[i % 2][j], tot);
      g[i] = min(g[i], f[i % 2][j]);
    }
  }
  int ans = 1000000000;
  for (int i = 0; i <= lim; i++) ans = min(ans, f[n % 2][i]);
  cout << ans << endl;
  return 0;
}
