记录编号	216848	评测结果	AAAAA
题目名称	混合牛奶	最终得分	100
用户昵称	520	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-12-31 22:18:31	内存使用	0.29 MiB

#include<stdio.h>
#include<stdlib.h>
void merge(int r1[][2],int r2[][2],int left,int right,int mid)
{
	int j,k;
	for(j=mid+1,k=left;left<=mid&&j<=right;k++)
	{   
		if(r1[left][0]<=r1[j][0])    
		  {r2[k][0]=r1[left][0];r2[k][1]=r1[left++][1];}
		else      
		  {r2[k][0]=r1[j][0];r2[k][1]=r1[j++][1];}  
	}   
	while(left<=mid)
	  {r2[k][0]=r1[left][0];r2[k++][1]=r1[left++][1];}
	while(j<=right)
	  {r2[k][0]=r1[j][0];r2[k++][1]=r1[j++][1];}
}
void m_sort(int r1[][2],int r2[][2],int left,int right)
{
	int r3[5001][2]={0};
	int mid=(left+right)/2;
	if(left==right)
	{
		r2[left][0]=r1[left][0];
		r2[left][1]=r1[left][1];
	}
	else
	{
		m_sort(r1,r3,left,mid);
		m_sort(r1,r3,mid+1,right);
		merge(r3,r2,left,right,mid);
	}
}
int main()
{
	freopen("milk.in","r",stdin);
	freopen("milk.out","w",stdout);
	int n,m,sum=0,c=0,r[5001][2]={0};
	scanf("%d%d",&n,&m);
	if(n==0){printf("0\n");return 0;}
	for(int i=0;i<m;i++)
	  scanf("%d%d",&r[i][0],&r[i][1]);
	m_sort(r,r,0,m-1);
	for(int i=0;i<m;i++)
	{ 
		if(r[i][1]+sum<=n)
		  c+=r[i][0]*r[i][1];
		else
		{
			c+=(n-sum)*r[i][0];
			break;
		}
		sum+=r[i][1];
	}
	printf("%d\n",c);
	return 0;
}