Informatica Online Judge

  Mixing Milk (우유 섞기) [0257 / 0101]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 84   Total Tried : 91


The Champion of this Problem (C++) : junelee107 - 0ms / 535byte
My Best Submission (C++) : N/A

[]

Background

우유를 포장해서 파는 것은 이익이 별로 남지 않기 때문에, 원재료(우유)의 값을 최대한 낮게 유지하는 것이 중요하다. Merry유업이 가능한한 싼 방법으로 우유를 얻을 수 있도록 도와주자.

Merry유업은 우유를 사오는 여러 농부가 있으며, 각각의 농부는 (잠정적으로) 우유 공장에 우유를 팔때 다른 가격을 받는다. 또한, 하루에 소한마리가 생산하는 우유의 량이 한정되어있기 때문에, 농부들은 하루에 팔만큼의 우유만 가지고 있다. 매일, Merry유업은 각 농부들에게서 그들의 생산할 수 있는 우유 전부 혹은 일부를 모아 구입할 수 있다.

Merry 유업의 일일 우유 필요량, 각각의 농부에게서 얻을 수 있는 우유의 량과 우유 1갤런에 대한 가격이 주어질때, Merry유업의 우유 필요량을 채울 수 있는 최소의 금액을 계산하여라.

주의: 농부들이 하루에 생산하는 우유의 총합은 Merry유업의 필요량을 충분히 만족시킬 것이다.

Input

첫 번째 줄에는 두개의 정수가 공백으로 구분된다. 첫 번째 값, N(0<=N<=2,000,000)은 Merry유업이 하루에 필요한 우유의 량이다. 두번째 값 M(0<=M<=5000)은 우유를 살 수 있는 농부의 수이다.
2번 줄부터 M+1번 줄까지 M개의 줄은 Pi와 Ai의 2개의 정수가 공백으로 구분되어 입력된다.

Pi는 i번째 농부가 받게되는 가격을 센트단위로 표현한 것이다. ( 0 <= Pi <= 1,000 )
Ai는 i번 농부가 하루에 Merry유업에 우유를 팔 수 있는 양이다. ( 0 <= Ai <= 2,000,000 )

Output

Merry유업이 하루에 구매하는 우유값의 최소 비용을 나타내는 정수를 출력한다.

IO Example

입력
100 5
5 20
9 40
3 10
8 80
6 30

출력
630

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]