#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[150010];
int f[150010], g[150010];
short sum[150010][800];
int main() {
  int n, m, lim, i, j, cnt, val;
  scanf("%d%d", &n, &m);
  for (lim = 1; 2 + lim * (lim + 1) / 2 <= 3 * m; lim++)
    ;
  for (i = 1, cnt = 0; i <= m; i++) {
    scanf("%d%d", &a[i].first, &a[i].second);
    a[i].first = n - a[i].first + 1;
    swap(a[i].first, a[i].second);
    if (a[i].second > lim)
      cnt++, i--, m--;
    else
      sum[a[i].first][a[i].second]++;
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= lim; j++) {
      sum[i][j] += sum[i][j - 1];
    }
  }
  for (i = 1; i <= lim; i++) {
    for (j = 1; j <= i; j++) {
      g[i] += sum[j][i - j + 1];
    }
  }
  for (i = 1; i <= n; i++) f[i] = 1 << 30;
  for (i = 1; i <= n; i++) {
    f[i] = min(f[i], f[i - 1] + sum[i][lim] * 3);
    for (j = 1; j <= lim; j++) {
      if (j * (j + 1) / 2 + 2 <= g[j] * 3) {
        val = f[i - 1];
        for (int k = 1; k <= j; k++) {
          val += (sum[i + k - 1][lim] - sum[i + k - 1][j - k + 1]) * 3;
          f[i + k - 1] = min(f[i + k - 1], val + j * (j + 1) / 2 + 2);
        }
      }
    }
    for (j = 1; j < lim; j++) g[j] = g[j + 1] - sum[i][j + 1];
    g[lim] = 0;
    for (j = 1; j <= lim; j++) g[lim] += sum[i + j][lim - j + 1];
  }
  printf("%d\n", 3 * cnt + f[n]);
  return 0;
}
