Al Granjero Juan se le están terminando sus suministros y necesita comprar ~H~ ~(1 \leq H \leq 50,000)~ libras de heno para sus vacas.

El conoce ~N~ ~(1 \leq N \leq 100)~ proveedores de heno convenientemente numerados ~1..N~.

El primer proveedor vende paquetes que contienen ~P_i (1 \leq P_i \leq 5,000)~ libras de heno a un costo de ~C_i (1 \leq C_i \leq 5,000)~ dólares. Cada proveedor tiene un número ilimitado de paquetes disponibles, y los paquetes deben comprarse enteros.

Ayude a GJ a encontrar el costo mínimo necesario para comprar al menos ~N~ libras de heno.

Entrada

Línea~ 1~: Dos enteros separados por enteros ~N~ y ~H~

Líneas ~2..N+1~: La línea ~i+1~ contiene dos enteros separados por espacio: ~P_i~ y ~C_i~.

Salida

Línea ~1~: Un solo entero representando el costo mínimo que GJ necesita pagar para obtener al menos ~H~ libras de heno.

Ejemplo de Entrada

2 15
3 2
5 3

Ejemplo de Salida

9

Detalles de Salida

GJ Puede comprar tres paquetes del segundo proveedor para un costo total de ~9~.