记录编号	216897	评测结果	AAAAA
题目名称	混合牛奶	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-01-01 13:00:07	内存使用	0.37 MiB

#include<stdio.h>
#include<stdlib.h>
int a[5010][2]={0},b[5010][2]={0},m,n,ans=0;
void merge(int l,int r)
{
	int mid=(l+r)/2,i=l,p=l,q=mid+1;
	while(p<=mid||q<=r)
	  if(q>r||p<=mid&&a[p][0]<=a[q][0])
	    {
		  b[i][0]=a[p][0];
		  b[i++][1]=a[p++][1];
	    }
	  else
	    {
		  b[i][0]=a[q][0];
		  b[i++][1]=a[q++][1];
	    }
	  for(i=l;i<=r;i++)
	    {
		  a[i][0]=b[i][0];
		  a[i][1]=b[i][1];
	    }
}
void msort(int l,int r)
{
	if(l>=r)
	  return;
	int mid=(l+r)/2;
	msort(l,mid);
	msort(mid+1,r);
	merge(l,r);
}
int main()
{
	freopen("milk.in","r",stdin);
	freopen("milk.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++)
	  scanf("%d%d",&a[i][0],&a[i][1]);
	msort(0,n-1);
	for(int i=0;i<n;i++)
	  if(a[i][1]>=m)
	    {ans+=a[i][0]*m;break;}
	  else
	    {
		  ans+=a[i][1]*a[i][0];
		  m-=a[i][1];
		}
	printf("%d",ans);
	return 0;
}