#include <bits/stdc++.h>
using namespace std;
int dp1[100500];
int dp2[100500];
int pref[100500];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> g[100500];
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    g[a - b + 1].push_back(n - a + 1);
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end());
  }
  for (int i = 0; i < 100500; i++) {
    dp1[i] = 1e9;
    dp2[i] = 1e9;
  }
  dp1[0] = 0;
  int maxK = min(n, (int)sqrt(6 * m) + 5);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= maxK; j++) {
      int cnt = g[i].size() -
                (upper_bound(g[i].begin(), g[i].end(), j) - g[i].begin());
      dp2[j] =
          min(pref[j + 1] + j * (j + 1) / 2 + (j == 0 ? 0 : 2), dp1[j + 1]) +
          3 * cnt;
    }
    pref[0] = dp2[0];
    for (int j = 1; j <= maxK + 1; j++) {
      pref[j] = min(pref[j - 1], dp2[j]);
    }
    for (int j = 0; j <= maxK + 1; j++) {
      dp1[j] = dp2[j];
      dp2[j] = 1e9;
    }
  }
  int res = 3 * m;
  for (int i = 0; i <= maxK; i++) {
    res = min(res, dp1[i]);
  }
  cout << res;
}
