#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1 << 30;
struct Node {
  int x, y;
} s[100100];
int n, m, K, ans, cnt;
int sum[100100], f[2][100100], Max[100100];
int cost(int x) { return x == 0 ? 0 : x * (x + 1) / 2 + 2; }
bool cmp(Node x, Node y) { return x.x < y.x; }
int main() {
  cin >> n >> K;
  int x, y;
  m = 1;
  while (2 + m * (m + 1) / 2 < 3 * K) m++;
  m = min(m, n);
  for (int i = 1; i <= K; i++) {
    scanf("%d %d", &x, &y);
    x -= n - m;
    ans += 3;
    if (x >= 1) {
      x = abs(x + (n - m) - y) + 1;
      s[++cnt] = (Node){x, y};
    }
  }
  int opt = 1, L, R, str = 1;
  sort(s + 1, s + cnt + 1, cmp);
  while (s[str].x == 1 && str <= cnt) sum[s[str].y] += 3, str++;
  for (int i = n + 1; i >= n - m + 1; i--) sum[i] += sum[i + 1];
  for (int i = n - m + 1; i <= n + 1; i++) f[0][i] = -cost(n - i + 1) + sum[i];
  for (int t = 2; t <= n; t++) {
    opt ^= 1;
    t--;
    L = max(1, n - m + 1 - t + 1), R = n - t + 2;
    Max[R + 1] = 0;
    for (int i = R; i >= L; i--) Max[i] = max(Max[i + 1], f[opt][i]);
    t++;
    if (max(1, n - m + 1 - t + 1) < L)
      f[opt][max(1, n - m + 1 - t + 1)] = -Maxn;
    L = max(1, n - m + 1 - t + 1), R = n - t + 2;
    for (int i = R + 1; i >= L; i--) sum[i] = 0;
    while (s[str].x == t && str <= cnt) sum[s[str].y] += 3, str++;
    for (int i = R; i >= L; i--) sum[i] += sum[i + 1];
    for (int i = R; i >= L; i--)
      f[opt ^ 1][i] = max(f[opt][i], Max[i] - cost(R - i)) + sum[i];
  }
  opt ^= 1;
  int MMax = 0;
  for (int i = 1; i <= 2; i++) MMax = max(f[opt][i], MMax);
  cout << ans - MMax;
}
