Farmer John veut de nouvelles vaches ! Il y en a $N$ à vendre, $1 \le N \le 50,000$, et FJ ne peut dépasser son budget $M$, $1 \le M \le 10^{14}$. La vache $i$ coûte $P_{i}$, $1 \le P_{i} \le 10^9$. Ses $K$ coupons, $1 \le K \le N$, permettent de payer la vache $i$ au prix $C_{i}$, $1 \le C_{i} \le P_{i}$. Un seul coupon par vache.

Combien de vaches FJ peut-il acheter au maximum ?

Entrée

• Ligne $1$ : entiers $N$, $K$, $M$ séparés par des espaces.

• Lignes $2..N+1$ : la ligne $i+1$ contient les entiers $P_{i}$ et $C_{i}$.

Sortie

• Ligne $1$ : un entier, le nombre maximal de vaches achetables.

Exemples

Entrée 1

4 1 7
3 2
2 2
8 1
4 3

Sortie 1

3

Remarque

FJ a $4$ vaches, $1$ coupon et un budget de $7$.

Il utilise le coupon sur la vache $3$ et achète $1$, $2$, $3$ pour $3 + 2 + 1 = 6$.

Auteurs du problème : Neal Wu et Mark Gordon, 2012