Farmer John braucht neue Kühe! Es gibt $N$ zum Verkauf, $1 \le N \le 50,000$. FJ darf sein Budget $M$, $1 \le M \le 10^{14}$, nicht überschreiten. Kuh $i$ kostet $P_{i}$, $1 \le P_{i} \le 10^9$. Er hat $K$ Gutscheine, $1 \le K \le N$, und ein Gutschein für Kuh $i$ ersetzt den Preis durch $C_{i}$, $1 \le C_{i} \le P_{i}$. Höchstens ein Gutschein pro Kuh.

Wie viele Kühe kann FJ höchstens kaufen?

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $N$, $K$, $M$.

• Zeilen $2..N+1$: Zeile $i+1$ enthält ganze Zahlen $P_{i}$ und $C_{i}$.

Ausgabe

• Zeile $1$: eine ganze Zahl, die maximal bezahlbare Anzahl Kühe.

Beispiele

Eingabe 1

4 1 7
3 2
2 2
8 1
4 3

Ausgabe 1

3

Hinweis

FJ hat $4$ Kühe, $1$ Gutschein und Budget $7$.

Er verwendet den Gutschein für $3$ und kauft $1$, $2$, $3$ für $3 + 2 + 1 = 6$.

Aufgabenautoren: Neal Wu und Mark Gordon, 2012