프로그램 명: usa_nochange
제한시간: 1 초
농부 존은 그의 농장에 물품들을 구입하기 위해 마트에 있습니다.
그는 현재 K개의 지폐가 있으며 (1 <= K <= 16), 각 지폐는 1 이상 100,000,000 이하의 가치를 지닙니다.
농부 존은 N개의 물품들을 순차적으로 사고 싶어하는데, i번째 물품의 비용은 c(i)입니다. (1 <= c(i) <= 10,000)
그는 쇼핑을 하는 중간중간에 계산을 하지 않은 물품들을 계산합니다. (이 때 물품 비용의 합보다 지불하는 지폐의 합이 더 커야합니다.)
불행히도, 마트에는 거스름돈이 없는 관계로 존은 더 큰 비용을 지불해도 거스름돈을 돌려받지 못합니다.
N개의 물품을 구입한 이후에 존에게 남은 돈의 최댓값을 구해주세요.
입력
-
첫 번째 줄에는 두 정수 K와 N이 주어집니다.
-
두 번째 줄부터 K개의 줄에는 존의 지폐들의 가치가 순서대로 주어집니다.
-
세 번째 줄부터 N개의 줄에는 존이 사려고 하는 물품들의 가격들이 주어집니다.
물건을 살 때마다 화폐는 무조건 한개만 써야 합니다.
출력
N개의 물건을 구입한 후 남은 돈의 최댓값을 출력하세요. 만약, 모든 물품을 살 수 없다면 -1을 출력하세요.
입출력 예
입력
3 6
12
15
10
6
3
3
2
3
7
출력
12
입출력 보충
(6 3)(3 2 3 7)로 묶어서 첫 번째 괄호를 가치 10의 지폐로 지불하고, 두 번째 괄호를 가치 15의 지폐로 지불하게 되면 모든 물건을 구입하였고, 가치 12의 지폐를 사용하지 않았으므로 남는 최댓값은 12가 됩니다.
Farmer John is at the market to purchase supplies for his farm. He has in
his pocket K coins (1 <= K <= 16), each with value in the range
1..100,000,000. FJ would like to make a sequence of N purchases
(1 <= N <= 100,000), where the ith purchase costs c(i) units of money
(1 <= c(i) <= 10,000). As he makes this sequence of purchases, he can
periodically stop and pay, with a single coin, for all the purchases made
since his last payment (of course, the single coin he uses must be large
enough to pay for all of these). Unfortunately, the vendors at the market
are completely out of change, so whenever FJ uses a coin that is larger
than the amount of money he owes, he sadly receives no changes in return!
Please compute the maximum amount of money FJ can end up with after making
his N purchases in sequence. Output -1 if it is impossible for FJ to make
all of his purchases.
INPUT FORMAT:
-
* Line 1: Two integers, K and N.
-
* Lines 2..1+K: Each line contains the amount of money of one of FJ's
coins.
-
* Lines 2+K..1+N+K: These N lines contain the costs of FJ's intended
purchases.
SAMPLE INPUT :
3 6
12
15
10
6
3
3
2
3
7
INPUT DETAILS:
FJ has 3 coins of values 12, 15, and 10. He must make purchases in
sequence of value 6, 3, 3, 2, 3, and 7.
OUTPUT FORMAT:
* Line 1: The maximum amount of money FJ can end up with, or -1 if FJ
cannot complete all of his purchases.
SAMPLE OUTPUT :
12
OUTPUT DETAILS:
FJ spends his 10-unit coin on the first two purchases, then the 15-unit
coin on the remaining purchases. This leaves him with the 12-unit coin.
출처:usaco/2013NOV/gold
번역:Fate
[질/답]
[제출 현황]
[푼 후(0)]