#include <bits/stdc++.h>
using namespace std;
template <typename S, typename T>
inline bool smin(S &l, T r) {
  return r < l ? l = r, 1 : 0;
}
template <typename S, typename T>
inline bool smax(S &l, T r) {
  return l < r ? l = r, 1 : 0;
}
constexpr int MOD = 1e9 + 7;
template <typename S>
inline S mod(S &l) {
  return l = (l % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}
void fileIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
constexpr int N = 1e5 + 10;
constexpr int SQ = 780;
int n, k;
vector<int> vec[N];
int bias, dp[2][SQ], pd[2];
inline void input() {
  cin >> n >> k;
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    vec[y].push_back(n - x + 1);
  }
}
inline void faze_0() {
  for (int i = 1; i < n + 1; i++) {
    sort(vec[i].begin(), vec[i].end());
    while (vec[i].size() && vec[i].back() >= SQ - 2) {
      bias++;
      vec[i].pop_back();
    }
  }
}
inline void faze_1() {
  memset(dp[0], 63, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 1; i < n + 1; i++) {
    int me = i & 1, num = 0;
    pd[me] = 1e9;
    for (int j = min(n - i + 1, SQ - 2); ~j; j--) {
      dp[me][j] = num * 3 + min(dp[me ^ 1][j + 1],
                                pd[me ^ 1] + (j ? 2 : 0) + j * (j + 1) / 2);
      smin(pd[me], dp[me][j]);
      if (vec[i].size() && vec[i].back() == j) {
        num++;
        vec[i].pop_back();
      }
    }
  }
}
int main() {
  input();
  faze_0();
  faze_1();
  cout << 3 * bias + pd[n & 1] << endl;
  return 0;
}
