Problem : 312 - Mixing Milk

Problem Statistics

Solved Member: 30　　Submission: 55　　User Tried: 32

Statement:

The Merry Milk Makers company 能像眾多農夫購買牛乳，但每個農夫每單位所賣的牛乳價錢都不盡一樣。每個農夫所擁有牛的數量不等，因此每天可產出的牛乳量也不盡相同，每天 The Merry Milk Makers company 可以向農夫i購買x單位牛乳，其中x<=Ai(農夫i每天可產出的牛乳量)。

農夫i所賣每單位牛乳的價錢為 Pi
農夫i每天產出 Ai 單位牛乳

The Merry Milk Makers company 每天需要 N 單位的牛乳。
總共有 M 位農夫。

保證所有農夫每天產出的牛乳總和不會小於 N。

Input:Output:

第一行有兩個整數：
N(0 <= N <= 2,000,000) M(0 <= M <= 5,000)

接下來有M行，每行有兩個整數：
Pi (0 <= Pi <= 1,000) Ai (0 <= Ai <= 2,000,000)

一個整數，代表 The Merry Milk Makers company 每天購足牛乳所需花費的最小金額

Sample Input:Sample Output:

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

630

Source:

USACO Training

Problem Setter

andrew704

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	14
2	1000ms	65536kb	14
3	1000ms	65536kb	14
4	1000ms	65536kb	14
5	1000ms	65536kb	14
6	1000ms	65536kb	15
7	1000ms	65536kb	15