#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline void mine(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
inline void maxe(T1 &x, T2 y) {
  if (x < y) x = y;
}
ostream &operator<<(ostream &a, const vector<int> &b) {
  for (auto k : b) cout << k << ' ';
  return a;
}
const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 100010;
const double EPS = 1e-9;
const int D = 781;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[MX];
vector<int> rest[MX];
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < k; i++) {
    int r, c;
    cin >> r >> c;
    rest[c - 1].push_back(n - r + 1);
  }
  fill(dp + 1, dp + MX, INF);
  for (int i = 0; i < n; i++) {
    sort(rest[i].begin(), rest[i].end());
    int it = 0;
    int mn = INF;
    for (int j = 0; j < min(D, n - i + 1); j++) {
      while (it < (int)rest[i].size() && rest[i][it] <= j) ++it;
      mine(mn, dp[j]);
      int add = mn + (j ? 2 + j * (j + 1) / 2 : 0);
      dp[j] = 3 * ((int)rest[i].size() - it) + min(dp[j + 1], add);
    }
  }
  int ans = min(dp[0], dp[1]);
  assert(ans <= 3 * k);
  cout << ans << '\n';
}
