P9977 [USACO23DEC] Bovine Acrobatics S

Farmer John has decided to have his cows perform acrobatics. First, FJ weighed his cows and found that they have $N$ ($1 \le N \le 2 \times 10^5$) distinct weights. Specifically, for all $i \in [1, N]$, there are $a_i$ cows whose weight is $w_i$ units ($1 \le a_i \le 10^9$, $1 \le w_i \le 10^9$). His most famous act requires the cows to form a **balanced cow tower**. A **cow tower** consists of some cows, where each cow stands on top of the next cow. A cow tower is **balanced** if and only if every cow being stepped on is at least $K$ ($1 \le K \le 10^9$) units heavier than the cow **directly** standing on it. Every cow may be used as part of a cow tower. If FJ wants to create at most $M$ ($1 \le M \le 10^9$) cow towers, what is the maximum number of cows that can be used as part of the cow towers?

The first line contains three space-separated integers $N$, $M$, and $K$. The next $N$ lines each contain two space-separated integers $w_i$ and $a_i$. It is guaranteed that all $w_i$ are distinct.

Print the maximum number of cows in the cow towers when FJ uses the best strategy.

### Sample Explanation 1 FJ can use cows of weights $5, 7, 9$ to create four balanced cow towers, and then use cows of weights $5, 7$ to create one more. ### Sample Explanation 2 FJ can use cows of weights $5, 9$ to create four balanced cow towers, and then use one cow of weight $7$ to create one more. Alternatively, he can use cows of weights $5, 9$ to create four balanced cow towers, and then use one cow of weight $5$ to create one more. ### Test Point Properties - Test points $3-5$ satisfy $M \le 5000$ and the total number of cows does not exceed $5000$. - Test points $6-11$ satisfy that the total number of cows does not exceed $2 \cdot 10^5$. - Test points $12-17$ have no additional constraints. Translated by ChatGPT 5