2008: [USACO 2023 December Contest Silver] Problem 1. Bovine Acrobatics

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have $N$ ($1\le N\le 2\cdot {10}^5$) distinct weights. In particular, for each $i\in [1,N]$, $a_i$ of his cows have a weight of $w_i$ ($1\le a_i\le {10}^9,1\le w_i\le {10}^9$).

His most popular stunt involves the cows forming balanced towers. A tower is a sequence of cows where each cow is stacked on top of the next. A tower is balanced if every cow with a cow directly above it has weight at least $K$ ($1\le K\le {10}^9$) greater than the weight of the cow directly above it. Any cow can be part of at most one balanced tower.

If FJ wants to create at most $M$ ($1\le M\le {10}^9$) balanced towers of cows, at most how many cows can be part of some tower?

The next $N$ lines contain two space-separated integers, $w_i$ and $a_i$. It is guaranteed that all $w_i$ are distinct.

3 5 2
9 4
7 6
5 5

14