Farmer John potrzebuje nowych krów! Sprzedaje się $N$ krów, $1 \le N \le 50,000$, a FJ nie może przekroczyć budżetu $M$, $1 \le M \le 10^{14}$. Krowa $i$ kosztuje $P_{i}$, $1 \le P_{i} \le 10^9$. Ma $K$ kuponów, $1 \le K \le N$, a kupon na krowę $i$ zmienia cenę na $C_{i}$, $1 \le C_{i} \le P_{i}$. Tylko jeden kupon na krowę.

Ile krów maksymalnie może kupić FJ?

Wejście

• Wiersz $1$: całkowite $N$, $K$, $M$ oddzielone spacjami.

• Wiersze $2..N+1$: wiersz $i+1$ zawiera całkowite $P_{i}$ i $C_{i}$.

Wyjście

• Wiersz $1$: liczba całkowita, maksymalna liczba krów do kupienia.

Przykład

Wejście 1

4 1 7
3 2
2 2
8 1
4 3

Wyjście 1

3

Uwagi

FJ ma $4$ krowy, $1$ kupon i budżet $7$.

Używa kuponu na $3$, kupuje $1$, $2$, $3$ za $3 + 2 + 1 = 6$.

Autorzy zadania: Neal Wu i Mark Gordon, 2012