#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int sum = 0, t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    sum = sum * 10 + ch - '0';
    ch = getchar();
  }
  return sum * t;
}
int n, k;
vector<int> c[100005];
int f[100005], sum[100005], cst[100005];
int main() {
  n = read(), k = read();
  for (int i = 1; i <= k; i++) {
    int x = n - read() + 1, y = read();
    c[y].push_back(x);
  }
  memset(f, -0x3f, sizeof(f));
  for (int i = 1; i <= n; i++) {
    int t = min(n - i + 1, 780);
    memset(sum, 0, sizeof(sum));
    cst[0] = max(f[0], 0);
    for (int j = 0; j < c[i].size(); j++)
      if (c[i][j] <= t) sum[c[i][j]] = 1;
    for (int j = 1; j <= t + 1; j++) sum[j] += sum[j - 1];
    for (int j = 1; j <= t; j++) cst[j] = max(cst[j - 1], f[j]);
    f[0] = max(f[1], cst[0] - 3) + 3 * sum[1];
    f[0] = max(f[0], cst[0]);
    for (int j = 1; j <= t; j++)
      f[j] = max(f[j + 1], cst[j] - (j + 2) * (j + 1) / 2 - 2) + 3 * sum[j + 1];
  }
  printf("%d\n", k * 3 - f[0]);
}
