Informatica Online Judge

  돼지 저금통 [0984 / 03D8]

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


The Champion of this Problem (C++) : gs15120 - 14ms / 1360byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

자전거를 무척이나 갖고 싶어하는 철수는 오랫동안 돼지 저금통에 동전을 모았다. 저금통이 어느 정도 묵직해지긴 했는데 도대체 얼마가 들어있는지 도저히 알 수가 없었다. 그냥 무턱대고 저금통을 깨버리자니 충분한 돈이 모이지 않았을 수도 있다고 생각하니 그렇게는 할 수 없었다.

오직 가능한 것은 돼지 저금통의 무게를 재어서, 그 안에 얼마나 많은 액수의 동전이 있는지를 추측하는 것뿐이다. 돼지 저금통의 무게를 정확하게 측정할 수 있고, 모든 종류의 동전의 무게를 알 수 있다면 돼지 저금통에는 최소 얼마의 금액이 있다는 것을 알아낼 수 있다. 적당한 입력이 주어질 때 이를 찾아내는 프로그램을 작성하시오

Input

첫 줄에는 두 정수 E, F가 주어진다. 이 때 E는 빈 돼지 저금통의 무게이고, F는 동전으로 채워진 돼지 저금통의 무게이다. 각 테스트의 두 번째 줄에는 동전의 종류를 나타내는 정수 N이 주어진다. 다음 N줄 각각에는 P와 W가 주어지는데 P는 동전의 가치를 의미하고, W는 동전의 무게를 의미한다.

[입력값의 정의역]
1 <= E <= F <= 10,000
1 <= N <= 1,000
1 <= P <= 50,000
1 <= W <= 10,000

Output

주어진 무게의 동전들을 사용하여 얻어질 수 있는 최소의 금액을 출력한다. 만약 무게가 정확히 맞아 떨어질 수 없다면 대신 –1을 출력한다

IO Example

입력
10 110
2
1 1
30 50

출력
60

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