¡Farmer John necesita vacas nuevas! Se venden $N$, $1 \le N \le 50,000$, y FJ no puede superar su presupuesto $M$, $1 \le M \le 10^{14}$. La vaca $i$ cuesta $P_{i}$, $1 \le P_{i} \le 10^9$. Tiene $K$ cupones, $1 \le K \le N$, y usar uno en $i$ cambia el precio a $C_{i}$, $1 \le C_{i} \le P_{i}$. Solo un cupón por vaca.

¿Cuántas vacas puede comprar FJ como máximo?

Entrada

• Línea $1$: enteros $N$, $K$, $M$ separados por espacios.

• Líneas $2..N+1$: la línea $i+1$ contiene enteros $P_{i}$ y $C_{i}$.

Salida

• Línea $1$: un entero, el máximo número de vacas que puede comprar.

Ejemplos

Entrada 1

4 1 7
3 2
2 2
8 1
4 3

Salida 1

3

Nota

FJ tiene $4$ vacas, $1$ cupón y presupuesto $7$.

Usa el cupón en $3$ y compra $1$, $2$, $3$ por $3 + 2 + 1 = 6$.

Autores del problema: Neal Wu y Mark Gordon, 2012