거스름돈

주혁은 시장에 장을 보기 위해 왔습니다. 그는 주머니에 K개의 동전을 가지고 있습니다 (1 <= K <= 16), 각각의 가치는 1..100,000,000의 범위에 있습니다. 주혁은 N개의 구매를 이어가고 싶습니다 (1 <= N <= 100,000). 여기서 i번째 구매는 c(i) 단위의 돈이 필요합니다 (1 <= c(i) <= 10,000). 이 구매를 계속하면서 그는 가끔 멈추고, 마지막 결제 이후로 구매한 모든 것을 한 동전으로 지불할 수 있습니다 (물론, 사용하는 단독 동전은 모든 비용을 지불할 수 있어야 합니다). 불행히도, 시장의 판매자들은 거스름돈이 없기때문에, 주혁이 돈을 더 많이 내면 거스름돈으로 받지 못합니다!

주혁이 N개의 구매를 순서대로 한 후에 얻을 수 있는 최대 금액을 계산해주세요. 만약 주혁이 모든 구매를 할 수 없다면 -1을 출력해주세요.

• 첫 번째 줄 1: 두 정수, K와 N.
• 두 번째 줄..1+K 번째 줄 : 각 줄은 주혁의 동전 하나의 돈의 양을 포함합니다.
• 2+K 번째 줄..1+N+K 번째 줄 : 이 N 줄들은 주혁이 구매하고자 하는 물품들의 비용을 포함합니다.

• 첫 번째 줄 : 주혁이 얻을 수 있는 최대 금액, 또는 주혁이 모든 구매를 완료할 수 없는 경우에는 -1.