#include <bits/stdc++.h>
const size_t Size = 1e5 + 5;
const size_t SqrtS = 775 + 5;
int f[Size];
int sum[Size];
int cost[Size];
std::vector<int> d[Size];
int n, k;
int main(void) {
  std::scanf("%d%d", &n, &k);
  for (int i = 1, x, y; i <= k; ++i) {
    std::scanf("%d%d", &x, &y);
    d[y].push_back(n - x + 1);
  }
  int sqrtK = SqrtS;
  std::memset(f, -0x3f, sizeof f);
  for (int i = 1, lim; i <= n; ++i) {
    std::memset(sum, 0, sizeof sum);
    lim = std::min(n + 1 - i, sqrtK);
    for (int j = d[i].size() - 1; j >= 0; --j)
      if (d[i][j] <= lim) sum[d[i][j]] = 1;
    for (int j = 1; j <= lim + 1; ++j) sum[j] += sum[j - 1];
    cost[0] = std::max(0, f[0]);
    for (int j = 1; j <= lim; ++j) cost[j] = std::max(cost[j - 1], f[j]);
    f[0] = std::max(cost[0], std::max(f[1], cost[0] - 3) + 3 * sum[1]);
    for (int j = 1; j <= lim; ++j)
      f[j] = std::max(f[j + 1], cost[j] - (j + 2) * (j + 1) / 2 - 2) +
             3 * sum[j + 1];
  }
  std::printf("%d\n", k * 3 - f[0]);
  return 0;
}
