Informatica Online Judge

  사랑의 묘약 [0649 / 0289]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

창환이는 좋아하는 아이가 한 명 있다.

그런데 그 아이는 인기가 많아서 넘보는 사람이 너무 많았다.

창환이는 사랑을 독차지하기 위해서 고민하던 중 사랑의 묘약에 대해 알게 되었다.
사랑의 묘약을 만들기 위해 재료를 구하는 중, 어떤 액체 물질 A와 B가 일정 비율(m:n)로 혼합된 용액이 L만큼 필요하다는 것을 알게 된 창환이는 자기가 구할 수 있는 혼합물을 찾아봤지만 다른 비율로 혼합된 혼합물들만 많이 있었다.

혼합물들의 용량이 나와 있어서 각각 혼합물에 A와 B가 얼마나 들어있는지 알 수 있기 때문에 창환이는 용액을 혼합해서 원하는 비율을 갖는 용액을 만들려고 한다. (각각 혼합물을 계량할 수 없기 때문에 사용한 혼합물을 모두 사용해야 한다.)

버리는 용액을 줄이기 위해 최소한의 용액만을 만들려고 할 때, 만들어진 용액의 용량은 얼마나 될까?

Input

첫째 줄에 A와 B의 비율인 m, n과 필요한 용액의 양 L이 주어진다.
둘째 줄에 혼합물 용액의 수 K가 주어진다.
셋째 줄부터 차례로 혼합물 용액에 들어있는 A와 B의 양 Xi, Yi이 주어진다.
(0<=m, n<=100, L<=2000, K<=25, Xi, Yi<=200, 입력되는 수는 모두 음이 아닌 정수이다)

Output

주어진 용액으로부터 만들 수 있는 A와 B가 m:n으로 혼합된 용액 양의 최솟값을 출력한다.
용액을 만들 수 없는 경우에는 –1을 출력한다.

IO Example

입력
3 5 20
5
5 13
6 9
3 7
6 8
10 10

출력
24

설명) 3번째 용액과 4번째 용액을 혼합하면 A가 9, B가 15가 되어서 혼합된 용액의 양은 20을 넘고 용액의 A와 B의 비는 3:5이다.

출제 : 조영성(GSHS-29th, 2012알고리즘수행평가)

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