#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3fffffff;
const int maxn = 100000 + 5, maxh = 800;
int n, k;
int f[maxh], g[maxh];
vector<int> P[maxn];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1, iend = k; i <= iend; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    P[y].push_back(n - x + 1);
  }
  for (int i = 1, iend = n; i <= iend; ++i) sort(P[i].begin(), P[i].end());
  int hgt = sqrt(6 * k) + 5;
  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  for (int i = 1, iend = n; i <= iend; ++i) {
    memcpy(g, f, sizeof f);
    memset(f, 0x3f, sizeof f);
    int minf = 0, pt = 0;
    for (int j = 0, jend = hgt; j <= jend; ++j) {
      if (pt < P[i].size() && P[i][pt] == j) pt++;
      if (g[j] < g[minf]) minf = j;
      f[j] = min(g[j + 1], g[minf] + (j ? j * (j + 1) / 2 + 2 : 0)) +
             (P[i].size() - pt) * 3;
    }
  }
  int ans = inf;
  for (int i = 0, iend = hgt; i <= iend; ++i) ans = min(ans, f[i]);
  printf("%d", ans);
  return 0;
}
