#include <bits/stdc++.h>
using namespace std;
vector<int> a[100005];
int n, m;
int f[1005];
int s[1005];
int mx;
int main() {
  scanf("%d%d", &n, &m);
  mx = sqrt(6 * m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[y - x + n].push_back((((n - x) < (mx)) ? n - x : mx));
  }
  for (int i = 1; i <= n; i++) {
    memset(s, 0, sizeof(s));
    if (a[i].size())
      for (int j = 0; j <= a[i].size() - 1; j++) s[a[i][j]]++;
    for (int j = mx - 1; j >= 0; j--) s[j] += s[j + 1];
    int now = f[0] + s[0] * 3;
    for (int j = (((i) < (mx)) ? i : mx); j >= 1; j--) {
      now = (((now) < (f[j - 1] + j * (j + 1) / 2 + 2 + s[j] * 3))
                 ? now
                 : f[j - 1] + j * (j + 1) / 2 + 2 + s[j] * 3);
      f[j] = (((now) < (f[j - 1] + s[j] * 3)) ? now : f[j - 1] + s[j] * 3);
    }
    f[0] = now;
  }
  printf("%d", f[0]);
  return 0;
}
