거스름돈 없음

농부 존이 농장에 쓸 물건을 사려고 시장에 왔다. 주머니에는 동전 $K$개 ($1 \le K \le 16$)가 있고, 각 동전의 가치는 $1$ 이상 $10^8$ 이하의 정수다. 존은 정해진 순서대로 $N$번 ($1 \le N \le 10^5$) 물건을 사려고 하며, $i$번째 구매에는 $c_i$ ($1 \le c_i \le 10^4$)만큼 돈이 든다.

구매를 이어가는 도중에 존은 언제든 멈춰서 계산할 수 있다. 계산할 때는 동전 하나를 내고, 지난번 계산 이후에 산 물건 값을 한꺼번에 치른다. 물론 그 동전 하나로 그 금액을 전부 낼 수 있어야 한다. 시장 상인에게는 거스름돈이 전혀 없어서, 내야 할 금액보다 가치가 큰 동전을 내면 차액은 그대로 사라진다.

한 번 쓴 동전은 이렇게 손에서 없어지므로, 마지막에 존에게 남는 돈은 한 번도 쓰지 않은 동전의 가치를 모두 더한 값이다. $N$번의 구매를 순서대로 모두 마쳤을 때 존에게 남는 돈의 최댓값을 구하라. 모든 구매를 마칠 수 없으면 $-1$을 출력한다.

• 첫째 줄: 정수 $K$와 $N$이 주어진다.
• 둘째 줄부터 $1+K$번째 줄까지: 각 줄에 존이 가진 동전 하나의 가치가 주어진다.
• $2+K$번째 줄부터 $1+N+K$번째 줄까지: 이 $N$개 줄에 존이 사려는 물건의 비용이 순서대로 주어진다.

• 첫째 줄: 존이 $N$번의 구매를 모두 마친 뒤 남길 수 있는 돈의 최댓값을 출력한다. 모든 구매를 마칠 수 없으면 $-1$을 출력한다.

예제에서 존에게는 가치가 $12$, $15$, $10$인 동전 세 개가 있고, 비용이 $6$, $3$, $3$, $2$, $3$, $7$인 구매를 순서대로 해야 한다. 처음 두 구매는 $10$짜리 동전으로 계산하고 ($6 + 3 = 9 \le 10$), 남은 네 구매는 $15$짜리 동전으로 계산하면 ($3 + 2 + 3 + 7 = 15$) $12$짜리 동전이 그대로 남는다.