Puesto que empacar leche es un negocio de tan bajo margen de ganancias, es importante mantener el precio de la materia prima (leche) tan bajo como sea posible. Ayude a Felices Lecheros a obtener la leche que ellos necesitan de la manera más barata posible.

La compañía Felices Lecheros tiene varios granjeros a los cuales ellos pueden comprar leche, y cada uno tiene un precio (potencialmente) diferente con el cual él vende a la planta envasadora de leche. Aún más, como las vacas solo pueden producir una cantidad limitada en un día, los granjeros solo tienen una cantidad limitada de leche para vender por día. Cada día, Felices Lecheros puede comprar una cantidad entera de leche de cada granja, menor o igual al límite de la granja.

Dado el requerimiento diario de Felices Lecheros, junto con el costo por galón y la cantidad disponible de leche para cada granja, calcule la cantidad mínima de dinero que se necesita para cumplir los requerimientos de Felices Lecheros. El total de la leche producida por día por los granjeros será suficiente para cumplir las demandas de los Felices Lecheros.

Entrada

• Línea 1: Dos enteros, ~N~ y ~M~. El primer valor, ~N~, es la cantidad de leche que Felices Lecheros quiere por día. El segundo, ~M~, es el número de granjeros a los cuales les pueden comprar.
• Líneas 2 a M+1: Las siguientes ~M~ lìneas contienen dos enteros, ~P_i~ y ~A_i~. ~P_i~ es el precio en centavos que el granjero ~i~ cobra. ~A_i~ es la cantidad de leche que el granjero ~i~ puede vender a Felices Lecheros por día.

Salida

Una sola línea con un solo entero que es la mínima cantidad de dinero con el que Felices Lecheros puede comprar su leche para un día

Restricciones

• ~0 \leq N \leq 2,000,000~
• ~0 \leq M \leq 5,000~
• ~0 \leq P_i \leq 1,000~
• ~0 \leq A_i \leq 2,000,000~

Ejemplo de Entrada

100 5
5 20
9 40
3 10
8 80
6 30

Ejemplo de Salida

630