#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int block = 800;
int n, k, z;
vector<int> pos[maxn];
int suf[maxn], dp[2][maxn], pre[2][maxn];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= (k); i++) {
    int r, c;
    scanf("%d%d", &r, &c);
    pos[r - c + 1].push_back(c);
  }
  int m = 1;
  while (m * (m + 1) / 2 < 3 * k) m++;
  for (int i = 1; i <= (m); i++) dp[z][i] = -int(1e9);
  for (int i = 1; i <= (n); i++) {
    z ^= 1;
    for (int j = 0; j < (m + 1); j++) suf[j] = 0;
    for (int j = 0; j < (int(pos[i].size())); j++)
      if (n - i + 1 - pos[i][j] + 1 <= m) suf[n - i + 1 - pos[i][j] + 1]++;
    for (int j = 1; j <= (m); j++) suf[j] += suf[j - 1];
    for (int j = 0; j < (m + 1); j++) {
      dp[z][j] = -int(1e9);
      if (j <= n - i + 1) {
        if (j + 1 <= m) dp[z][j] = dp[z ^ 1][j + 1] + suf[j] * 3;
        dp[z][j] = max(dp[z][j], pre[z ^ 1][j] + suf[j] * 3 - j * (j + 1) / 2 -
                                     2 * (j > 0));
      }
      if (!j)
        pre[z][j] = dp[z][j];
      else
        pre[z][j] = max(pre[z][j - 1], dp[z][j]);
    }
  }
  int ans = -int(1e9);
  for (int j = 0; j < (m + 1); j++) ans = max(ans, dp[z][j]);
  printf("%d\n", 3 * k - ans);
  return 0;
}
