#include <bits/stdc++.h>
enum { MAXN = 100000 + 5 };
const int LIMIT = 800;
const int oo = 0x3f3f3f3f;
template <typename T>
inline bool chkmin(T &first, T second) {
  return second < first ? first = second, true : false;
}
int n, k;
int *dp[MAXN];
std::vector<int> a[MAXN];
void clear() { memset(dp, 0x3f, sizeof dp); }
void exec() {
  int i, r, c, p, j, minx, last;
  scanf("%d%d", &n, &k);
  for (i = 0; i < k; ++i) {
    scanf("%d%d", &r, &c), --r, --c;
    a[c].push_back(r);
  }
  for (i = 0; i < n; ++i) std::sort(a[i].begin(), a[i].end());
  last = 0;
  dp[0] = new int[LIMIT];
  memset(dp[0], 0x3f, sizeof *dp[0] * LIMIT);
  dp[0][0] = 0;
  for (i = 0; i < n; ++i) {
    dp[i + 1] = new int[LIMIT];
    if (i >= 2) delete dp[i - 2];
    p = 0;
    last = minx = oo;
    for (j = LIMIT - 1; ~j; --j) chkmin(last, dp[i][j]);
    for (j = LIMIT - 1; ~j; --j) {
      while (p < ((int)(a[i]).size()) && n - a[i][p] > j) ++p;
      dp[i + 1][j] =
          std::min(minx, last + (j ? j * (j + 1) / 2 + 2 : 0)) + p * 3;
      chkmin(minx, dp[i][j]);
    }
  }
  printf("%d\n", std::min(dp[n][1], dp[n][0]));
}
int main() {
  if (fopen("D.in", "r") != NULL) {
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
  }
  exec();
  return 0;
}
