Aun sabiendo que podría acabar terriblemente mal, Alicia termina por llenar su mochila de más, lo que provoca que esta acabe por romperse. Por suerte, la mochila se rompió cuando Alicia aún no había salido de su casa, por lo que el incidente no fue más que un pequeño contratiempo que solventar. Para ello, se propone buscar una nueva mochila (por Amazon, no esperarías que fuera a salir a la calle, ¿no?).

Ya que va a adquirir una nueva mochila, Alicia ha pensado que no sería mala idea imponer un criterio, para que no se vuelva a romper. Con este propósito, Alicia fija una cantidad mínima de azúcar que tiene que poder llevarse en su mochila, y se dispone a buscar la mochila con el menor peso límite que le permita llevar la cantidad fijada. ¿Podrías ayudarla?

Entrada

La primera línea contendrá tres enteros: ~n~ (~1 \le n \le 7 \cdot 10^{3}~), el número de alimentos con los que cuenta Alicia en casa, ~k~ (~1 \le k \le 14 \cdot 10^{3}~), los gramos de azúcar mínimos que tiene que poder llevar en su mochila, y ~l~ (~1 \le l \le 49 \cdot 10^{6}~), el máximo peso límite mínimo que se puede llegar a dar.

Las siguientes ~n~ líneas contendrán dos enteros: ~s_{i}~ (~1 \le s_{i} \le 7 \cdot 10^{3}~), los gramos de azúcar en el ~i~-ésimo alimento, y ~w_{i}~ (~1 \le w_{i} \le 7 \cdot 10^{3}~), el peso del ~i~-ésimo alimento (~1 \le i \le n~).

Salida

Se ha de imprimir un entero ~m~, el peso límite mínimo que la mochila puede tener para llevar, al menos, ~k~ gramos de azúcar. Se garantiza que ~m \le l~.

Puntuación

• 50 puntos: ~l \le 14 \cdot 10^{3}~
• 50 puntos: Sin restricciones.