Balanced Cow Towers

Farmer John wants his cows to perform acrobatics by forming balanced cow towers. He has N different cow weights. For each i in \( [1,N] \), there are \( a_i \) cows of weight \( w_i \) (with \(1 \le a_i \le 10^9\) and \(1 \le w_i \le 10^9\)).

A cow tower is built by stacking cows one on top of the other. A tower is balanced if and only if for every cow that is stepped on (i.e. every cow except the top one), the cow directly above it is at least \(K\) units lighter. In other words, if a cow of weight \(x\) is directly on top of a cow of weight \(y\), then it must hold that \[ y + K \le x'\] (actually, written in terms of the order from top to bottom, if the tower is \(a_1, a_2, \ldots, a_\ell\) where \(a_1\) is the top cow and \(a_\ell\) is the bottom cow, then for every \(1 \le i < \ell\) the condition \[ a_{i+1} \ge a_i + K \] must hold). Every cow can be used in at most one tower.

Farmer John wishes to form at most M towers (\(1 \le M \le 10^9\)). What is the maximum number of cows that can be used as part of these towers?

Note: The input guarantees that the weights \(w_i\) are pairwise distinct.

inputFormat

The input consists of:

1. A single line containing three integers \(N, M, K\) separated by spaces.
2. Then \(N\) lines follow; the \(i\)-th line contains two integers \(w_i\) and \(a_i\) representing a weight and the number of cows with that weight.

It is guaranteed that \(1 \le N \le 2 \times 10^5\), \(1 \le a_i \le 10^9\), \(1 \le w_i \le 10^9\) (all \(w_i\) are distinct) and \(1 \le K \le 10^9\), \(1 \le M \le 10^9\).

outputFormat

Output a single integer, the maximum number of cows that can be used to form at most \(M\) balanced cow towers.

sample

3 2 3
1 3
4 2
7 1

5