牛奶包装是一个如此低利润的生意,以至于尽可能低地控制初级产品(牛奶)的价格变得十分重要。请帮助Merry的牛奶制造公司(Merry Milk Makers')以尽可能最廉价的方式取得他们所需的牛奶。Merry的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,Merry的牛奶制造公司从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。给出Merry牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算Merry的牛奶制造公司所要付出钱的最小值。
注意:每天农民生产的牛奶的总数对Merry的牛奶制造公司来说是足够的。
INPUT FORMAT:
(file milk.in)
第 1 行:二个整数, N 和 M。
第一个数值,N,(0<= N<=2,000,000)是Marry的牛奶制造公司的一天需要牛奶的数量。
第二个数值,M,(0<= M<=5,000)是提供牛奶的农民个数。
第 2 到 M+1 行:每行二个整数,Pi 和 Ai。
Pi(0<= Pi<=1,000) 是农民 i 的牛奶的价格。
Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。
OUTPUT FORMAT:
(file milk.out)
单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用。
input：
100 5
5 20
9 40
3 10
8 80
6 30
output：
630
【参考程序】：
/*
ID: XIONGNA1
PROG: milk
LANG: C++
*/
#include<iostream>
using namespace std;
struct node
{
int v,c;
} a[5001];
int n,m;
int cmp(const void *s,const void *t)
{
node i=*(node *)s,j=*(node *)t;
if (i.v!=j.v) return i.v-j.v;
else return j.c-i.c;
}
int main()
{
freopen("milk.in","r",stdin);
freopen("milk.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&a[i].v,&a[i].c);
qsort(a+1,m,sizeof(node),cmp);
int ans=0;
for (int i=1;i<=m;i++)
{
if (!n) break;
if (n>=a[i].c)
{
ans+=a[i].c*a[i].v;
n-=a[i].c;
}
else
{
ans+=n*a[i].v;
n=0;
}
}
printf("%d\n",ans);
return 0;
}