Farmer John's Payment Problem

Farmer John is at the market with K coins and wishes to make N purchases in sequence. The i^th purchase costs c(i) units. At any point during his purchases, he may stop and pay for all the purchases made since his last payment using a single coin. However, the coin used must have a value at least equal to the total cost accumulated since the last payment, and if the coin’s value exceeds the cost, no change is returned (i.e. the extra value is wasted).

You are given an integer K (with \(1 \le K \le 16\)) representing the number of coins, and a list of K coin values \(a_1, a_2, \dots, a_K\) where \(1 \le a_i \le 10^8\). Farmer John also needs to make N purchases (with \(1 \le N \le 10^5\)), where the cost of the i^th purchase is \(c(i)\) (\(1 \le c(i) \le 10^4\)).

John can decide when to pay for his purchases. Formally, if his previous payment was made just before purchase \(i\) (or if \(i = 1\), at the beginning), he may choose a coin with value \(a_j\) (which has not been used before) to pay for purchases \(i, i+1, \dots, j'\) as long as \[ \sum_{k=i}^{j'} c(k) \le a_j. \] He continues this process until all N purchases are completed. His goal is to maximize the total value of the coins that remain unused at the end. If it is impossible to cover all purchases with the available coins, output -1.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input is given as follows:

1. The first line contains an integer K, the number of coins.
2. The second line contains K space-separated integers representing the coin values.
3. The third line contains an integer N, the number of purchases.
4. The fourth line contains N space-separated integers, where the i^th integer denotes \(c(i)\), the cost of the i^th purchase.

outputFormat

Output a single integer, which is the maximum total value of coins remaining after making all purchases under an optimal payment strategy. If it is impossible to make all purchases, output -1.

sample

3
10 5 3
4
3 4 2 5

3