HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]

Problem D
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 143   Accepted Submission(s) : 61
Problem Description
그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서 XHD 는 가만히 있 지 않 을 것 이다.
  어느 날, 그 가 어려움 을 해결 할 좋 은 방법 을 고민 하고 있 을 때 갑자기 자신의 전가 의 보물 이 생각 났 다. 그것 은 회사 가 설립 되 었 을 때 아버지 가 축하 선물 로 보 낸 금 주머니 였 다. 서 아버 지 는 만부득이 할 때 열지 말 라 고 당부 하 셨 다."지금 이 가장 필요 한 때 아 닙 니까?"라 고 생각 하 며 XHD 가 정 성 스 럽 게 보관 하고 있 는 이 금 낭 을 찾 아 열 어 보 니 '항 성 북쪽 기슭 천인 동 에 보물 이 있다' 는 말 만 들 어 있 었 다.
  두말 하지 않 고 XHD 는 큰 주머니 를 들 고 출발 했 습 니 다. 이 천인 동 은 그 가 알 고 있 었 습 니 다. 어 렸 을 때 아버지 께 서 그 를 데 리 고 이 은밀 한 길목 에 오 셨 고 이것 은 천인 동 이 라 고 말씀 하 셨 습 니 다.그 는 이제 야 아버지 가 애당초 이 말의 뜻 을 알 게 되 었 다.
  약간의 인상 에 도 불구 하고 XHD 는 많은 정력 을 들 여서 야 이 매우 은밀 한 동굴 입 구 를 찾 았 다. 들 어가 보 니 거의 놀 랐 다. 정말 눈 이 어지럽다!하지만 아기 의 종류 가 적지 않 음 에 도 불구 하고 각 아기 의 양은 많 지 않 습 니 다. 물론 각 아기 단위 의 부피 가격 도 다 릅 니 다. HDU 를 구하 기 위해 서 는 지금 빨리 XHD 가 가장 많은 가 치 를 가 져 올 수 있 는 아 이 를 계산 해 주 시 겠 습 니까?(아이 가 분할 할 수 있다 고 가정 하고 분할 후의 가치 와 대응 하 는 부 피 는 정비례 한다)
 
Input
여러 개의 테스트 인 스 턴 스 를 입력 하 십시오. 각 인 스 턴 스 의 첫 번 째 줄 은 두 개의 정수 v 와 n (v, n < 100) 으로 각각 주머니 의 용량 과 아기 의 종 류 를 표시 합 니 다. 이 어 n 줄 은 각각 2 개의 정수 pi 와 mi (0 < PI, MI < 10) 를 포함 하여 특정한 아기 의 단가 와 대응 하 는 체 적 을 표시 하고 V 가 0 일 때 입력 을 끝 냅 니 다.div <>
 
Output
모든 테스트 인 스 턴 스 에 대해 XHD 를 출력 하면 얼마나 많은 가 치 를 가 져 올 수 있 는 아 이 를 출력 하 십시오. 모든 인 스 턴 스 의 출력 은 한 줄 을 차지 합 니 다.
 
Sample Input

    
    
    
    

     
     
     
     2 2
3 1
2 3
0

    
    
    
    

 
Sample Output

    
    
    
    

     
     
     
     5


     
     
     
     AC-code：
    
    
    
    
    
    
    
    

     
     
     
     
#include<stdio.h>
#include<algorithm>
using namespace std;

struct bao
{
	int pi,mi;
}ba[105];

bool cmp(bao a,bao b)
{
	return a.pi>b.pi;
}

int main()
{
	int v,n,i,sum;
	while(scanf("%d%d",&v,&n),v)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&ba[i].pi,&ba[i].mi);
		sort(ba,ba+n,cmp);
		sum=0;
		for(i=0;i<n;i++)
		{
			if(ba[i].mi<=v)
			{
				sum+=ba[i].pi*ba[i].mi;
				v-=ba[i].mi;
			}
			else
			{
				sum+=v*ba[i].pi;
				break;
			}
		}
		printf("%d
",sum);
	}
	return 0;
}