Tetris 2D

#include<bits/stdc++.h>
using namespace std;
int tree[1 << 22], M = 1, w;
bool lazy[1 << 22];
void propagacja(int v){
  lazy[v] = 0;
  lazy[v * 2] = lazy[v * 2 + 1] = 1;
  tree[v * 2] = tree[v * 2 + 1] = tree[v];
}
void maks(int a, int b, int v = 1, int p = 1, int k = M){
  if(p > b || k < a) return;
  if(lazy[v]) propagacja(v);
  if(p >= a && k <= b){
    w = max(w, tree[v]);
    return;
  }
  maks(a, b, v * 2, p, (p + k) / 2);
  maks(a, b, v * 2 + 1, (p + k) / 2 + 1, k);
}
void ustaw(int a, int b, int v = 1, int p = 1, int k = M){
  if(p > b || k < a) return;
  if(lazy[v]) propagacja(v);
  if(p >= a && k <= b){
    lazy[v] = 1;
    tree[v] = w + 1;
    return;
  }
  ustaw(a, b, v * 2, p, (p + k) / 2);
  ustaw(a, b, v * 2 + 1, (p + k) / 2 + 1, k);
  tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int d, n;
  cin >> d >> n;
  while(M <= d) M *= 2;
  for(int i = 0, l, x;i < n;i++, w = 0){
    cin >> l >> x;
    maks(x + 1, l + x);
    ustaw(x + 1, l + x);
  }
  cout << tree[1];
}