¡El Granjero Juan necesita vacas nuevas! Hay ~N~ vacas a la venta, y GJ tiene que gastar no más que su presupuesto de ~M~ unidades de dinero. La vaca ~i~ cuesta ~P_i~ unidades de moneda, pero GJ tiene ~K~ cupones, y cuando ella usa un cupón para comprar la vaca i, la vaca cuesta ~C_i~ en vez de ~P_i~. GJ puede usar únicamente un cupón por vaca, por supuesto.

¿Cuál es el máximo número de vacas que GJ puede comprar?

Entrada

• Lìnea 1: Tres enteros separados por espacios: ~N, K~ y ~M~.
• Lìneas 2..N+1: La línea i+1 contiene dos enteros: ~P_i~ y ~C_i~.

Salida

Un solo entero, el máximo número de vacas que GJ puede comprar.

Ewstricciones

• ~1 \leq N \leq 50,000~
• ~1 \leq M \leq 10^{14}~
• ~1 \leq P_i \leq 10^9~
• ~1 \leq K \leq N~
• ~1 \leq C_i \leq P_i~

Ejemplo de Entrada

4 1 7
3 2
2 2
8 1
4 3

Detalles de la Entrada: FJ tiene 4 vacas, 1 cupón, y un presupuesto de 7.

Ejemplo de Salida

3

Detalles de la Salida: GJ usa el cupón en la vaca 3 y compra las vacas 1, 2 y 3, para un costo total de ~3 + 2 + 1 = 6~.

USACO 2012 February Contest, Gold Division Problem 1. Cow Coupons