#include <bits/stdc++.h>
using namespace std;
const int width = 775;
int n, m, cost[width + 10];
int arr1[width + 10], arr2[width + 10], *f = arr1, *g = arr2;
vector<int> item[100010];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int r, c;
    scanf("%d %d", &r, &c);
    item[c].push_back(n + 1 - r);
  }
  for (int i = 1; i <= width; ++i) {
    cost[i] = cost[i - 1] + i;
  }
  for (int i = 1; i <= width; ++i) {
    cost[i] += 2;
  }
  for (int i = 1; i <= n; ++i) {
    vector<int> row = item[i];
    int iq = 0, inum = row.size();
    sort(row.begin(), row.end());
    if (i == 1) {
      for (int j = 0; j <= width; ++j) {
        for (; iq != inum && row[iq] <= j; ++iq)
          ;
        f[j] = iq * 3 - cost[j];
      }
    } else {
      int best = -1e9;
      for (int j = 0; j <= width && j <= n + 1 - i; ++j) {
        for (; iq != inum && row[iq] <= j; ++iq)
          ;
        best = max(best, g[j]);
        if (j == width) g[j + 1] = -1e9;
        f[j] = max(g[j + 1], best - cost[j]);
        f[j] += iq * 3;
      }
    }
    swap(f, g);
  }
  printf("%d\n", 3 * m - max(g[0], g[1]));
}
