- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
Sue is waiting in line at the grocery store. Being in a hurry, she wants to pay with exact change when she gets to the front of the line. However, she does not know how much her items are going to cost; instead, she only knows an upper bound C on their total cost. Given a list of the various coins Sue has in her pocket, your goal is to determine the minimum number of coins she must take out in order to ensure that she can make exact change for every amount from 1 to C.
The input test file will contain multiple cases. Each test case begins with a single line containing two integers C (where 1 ≤ C ≤ 1000000000) and m (where 1 ≤ m ≤ 1000), where C is the maximum amount for which Sue must be able to make change, and m is the number of unique coin denominations Sue has in her pocket. The next m lines each contain two numbers, vi (where 1 ≤ vi ≤ 1000) and ni (where 1 ≤ ni ≤ 1000), where vi is the value of the ith coin denomination, and ni is the number of coins of that denomination that Sue has in her pocket. Input is terminated by a single line containing the number 0; do not process this line.
For each test case, either print a single line containing the number of coins Sue must use in order to make exact change for all amounts up to C, or print “Not possible” if exact change cannot always be made with any combination of coins in Sue’s pocket.
4 2 2 1 1 3 9 3 1 5 8 2 7 1 0
3 Not possible
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.