시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 23 | 9 | 9 | 47.368% |
A certain currency is issued with N coin denominations. (That is, the currency has N types of coins.) Each coin denomination i has a monetary value of vi cents and a weight of wi grams, 1 ≤ i ≤ N. Two coin denominations may have the same value or the same weight, but not both. For given values of V and W, you are to find M, the minimum number of coins needed, such that these M coins have a total monetary value of V cents and a total weight of W grams. Set M to zero when there is no such a collection of coins. You may assume an infinite supply of coins for each denomination.
Example 1. Let the coin denominations be
i | vi | wi |
---|---|---|
1 | 1 | 1 |
2 | 2 | 1 |
3 | 4 | 1 |
4 | 8 | 1 |
5 | 16 | 1 |
6 | 32 | 1 |
7 | 64 | 1 |
8 | 128 | 1 |
and V = 141, W = 4. We have M = 4 because the 4 coins, one from each of the denominations 1, 3, 4, 8, have a monetary value 141 and weight 4.
Example 2. Let the coin denominations be
i | vi | wi |
---|---|---|
1 | 12 | 3 |
2 | 4 | 7 |
3 | 8 | 10 |
4 | 21 | 9 |
For V=11 and W=17, we have M = 0 because obviously there is no such a set of coins.
The input file contains N + 1 lines. The first line consists of the integers N, V and W in that order. Each of the subsequent N lines consists of 2 integers separated by a space describing one coin denomination: the first integer is the value of the coin in cents and the second integer is the weight of the coin in grams.
8 141 4 1 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1
4
4 11 17 12 3 4 7 8 10 21 9
0