天天看點

hdu 2111 Saving HDU

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

struct Thing
{
	int danjia;
	int tiji;
}thing[200];

int cmp(Thing a,Thing b)
{
	return a.danjia>b.danjia;
}

int main()
{
	int v,n;
	int i,j;
	while(scanf("%d",&v)!=EOF)
	{
		if(v==0)
		break;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&thing[i].danjia,&thing[i].tiji);
		}
		
		sort(thing,thing+n,cmp);
		
		int sum=0;
		for(i=0;i<n;i++)
		{
			if(v>=thing[i].tiji)
			{
				v-=thing[i].tiji;
				sum+=(thing[i].tiji*thing[i].danjia);
			}
			else
			{
				sum+=(v*thing[i].danjia);
				break;
			}
		}
		
		printf("%d\n",sum);
	}
	
	return 0;
}