#include <bits/stdc++.h>
using std::vector;
inline int getint() {
  register int n = 0;
  register char ch = getchar();
  for (; !(isdigit(ch)); ch = getchar())
    ;
  for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
  return n;
}
vector<int> point[100010];
int n, m, k, f[100010], cnt[100010];
int main() {
  n = getint();
  k = getint();
  m = (((n) < ((int)ceil(sqrt(6 * k)))) ? (n) : ((int)ceil(sqrt(6 * k))));
  for (int i = 0, x, y; i < k; i++) {
    x = getint();
    y = getint();
    point[n + y - x].push_back(n - x);
  }
  for (int i = 1; i <= n; i++) {
    memset(cnt, 0, sizeof(cnt));
    for (auto j : point[i]) cnt[(((j) < (m)) ? (j) : (m))]++;
    for (int j = m; j >= 0; j--) cnt[j] += cnt[j + 1];
    register int prex = cnt[0] * 3 + f[0];
    for (int j = m; j; j--) {
      prex =
          (((prex) < ((prex, f[j - 1] + cnt[j] * 3 + ((j * j + j) >> 1) + 2)))
               ? (prex)
               : ((prex, f[j - 1] + cnt[j] * 3 + ((j * j + j) >> 1) + 2)));
      f[j] = (((prex) < ((prex, f[j - 1] + cnt[j] * 3)))
                  ? (prex)
                  : ((prex, f[j - 1] + cnt[j] * 3)));
    }
    f[0] = prex;
  }
  printf("%d\n", f[0]);
  return 0;
}
