Farmer John vuole nuove mucche! Ce ne sono $N$ in vendita, $1 \le N \le 50,000$, e FJ non può superare il budget $M$, $1 \le M \le 10^{14}$. La mucca $i$ costa $P_{i}$, $1 \le P_{i} \le 10^9$. Ha $K$ buoni, $1 \le K \le N$, e usarne uno sulla mucca $i$ cambia il prezzo a $C_{i}$, $1 \le C_{i} \le P_{i}$. Solo un buono per mucca.

Quante mucche può comprare FJ al massimo?

Input

• Riga $1$: interi $N$, $K$, $M$ separati da spazi.

• Righe $2..N+1$: la riga $i+1$ contiene interi $P_{i}$ e $C_{i}$.

Output

• Riga $1$: intero, il massimo numero di mucche acquistabili.

Esempi

Input 1

4 1 7
3 2
2 2
8 1
4 3

Output 1

3

Nota

FJ ha $4$ mucche, $1$ buono e budget $7$.

Usa il buono su $3$ e compra $1$, $2$, $3$ per $3 + 2 + 1 = 6$.

Autori del problema: Neal Wu e Mark Gordon, 2012