No Change

Farmer John is at the market to buy supplies for his farm. He carries $K$ coins ($1 \le K \le 16$) in his pocket, and each coin has an integer value between $1$ and $10^8$. John plans to make $N$ purchases ($1 \le N \le 10^5$) in a fixed order, and purchase $i$ costs $c_i$ ($1 \le c_i \le 10^4$).

While he works through that sequence, John may stop at any point and pay. To pay he hands over a single coin, and that coin settles every purchase he made since his previous payment, so it has to be worth at least the total of those purchases. The vendors have no change at all, so when John hands over a coin worth more than he owes, the difference is gone.

A coin leaves his pocket for good once he uses it, so the money John is left with is the total value of the coins he never used. Compute the largest amount of money John can be left with after making all $N$ purchases in order. Print $-1$ if he cannot make all of his purchases.

• Line 1: two integers $K$ and $N$.
• Lines 2 through $1+K$: each line contains the value of one of John's coins.
• Lines $2+K$ through $1+N+K$: these $N$ lines contain the costs of John's intended purchases, in order.

• Line 1: print the largest amount of money John can be left with, or $-1$ if he cannot make all of his purchases.

In the example John has three coins worth $12$, $15$, and $10$, and he must make purchases of $6$, $3$, $3$, $2$, $3$, and $7$ in that order. He pays for the first two purchases with the $10$ coin ($6 + 3 = 9 \le 10$) and for the remaining four with the $15$ coin ($3 + 2 + 3 + 7 = 15$). The $12$ coin stays in his pocket.