Problem Description

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?

Input Format

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.

Output Format

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

3 5 2
9 4
7 6
5 5

14

3 5 3
5 5
7 6
9 4

9

Hint

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