#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, k, f[2][810], s[N], ps[N];
vector<int> vec[N];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    vec[y].push_back(x - y + 1);
    s[x - y + 1]++;
  }
  memset(f[0], 0xbf, sizeof(f[0]));
  f[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    memset(f[i & 1], 0xbf, sizeof(f[i & 1]));
    int mx = 0xbfbfbfbf;
    for (int j = 0, je = min(800, n - i + 1); j <= je; j++) {
      if (j > 0) ps[j] = ps[j - 1] + s[n - i + 1 - j + 1];
      mx = max(mx, f[(i & 1) ^ 1][j] - (j > 0 ? ps[j - 1] : 0) * 3);
      f[i & 1][j] = max(f[(i & 1) ^ 1][j + 1],
                        mx - (j ? (j * (j + 1) / 2 + 2) : 0) + ps[j] * 3);
    }
    for (int y : vec[i]) s[y]--;
  }
  printf("%d\n", 3 * k - max(f[n & 1][0], f[n & 1][1]));
  return 0;
}
