teddy online judge |
|
|
teddy es un oso de peluche |
Datos invalidos
80. La leche
Limite de tiempo : 1 seg. Total runs : 68 Aceptados : 25
Como empacar leche es un negocio de tan bajo margen de ganancia, es importante mantener el precio de la materia prima (leche) tan bajo como sea posible. Ayude a Felices Hacedores de Leche a obtener la leche que ellos necesitan de la manera más barata posible.
La compañia Felices Hacedores de Leche 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 Hacedores de Leche 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 Hacedores de Leche, 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 Hacedores de Leche.
Nota: El total de la leche producida por día por los granjeros será suficiente para cumplir las demandas de los Hacedores Felices de Leche.
FORMATO DE ENTRADA
La primer linea sera un numero con el total de casos de prueba. Cada caso de prueba se define de la siguiente manera:
Línea 1: : Dos enteros, N y M.El primer valor, N, (0 ≤ N ≤ 2,000,000) es la cantidad de leche que Hacedores Felices de Leche quiere por día. El segundo, M, (0 ≤ M ≤ 5,000) 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, Pi y Ai.
Pi (0 ≤ Pi ≤ 1,000) es el precio en centavos que el granjero i cobra.
Ai (0 ≤ Ai ≤ 2,000,000) es la cantidad de leche que el granjero i puede vender a Felices Hacedores de Leche por día.
FORMATO DE SALIDA
Una sola línea con un solo entero que es la mínima cantidad de dinero con el que Felices Hacedores de Leche puede comprar su leche para un día
ENTRADA Y SALIDA DE EJEMPLO
1 100 5 5 20 9 40 3 10 8 80 6 30 |
630 |