Efficient Coin Exchange

Farmer John wants to buy supplies worth T cents. There are N different coin denominations in circulation with values \(V_1, V_2, \dots, V_N\) (with \(1 \le V_i \le 120\)). Farmer John has \(C_i\) coins of value \(V_i\) (\(0 \le C_i \le 10^4\)). The shopkeeper has an unlimited supply of coins and always gives change using the minimum possible number of coins. John wishes to pay in such a way that the total number of coins that change hands (the coins John uses plus the coins received as change) is minimized. Note that John’s payment must be such that it is possible to give exact change. Output -1 if no valid payment exists.

Input Constraints:

• \(1 \le T \le 10^4\)
• \(1 \le N \le 100\)

Input Format:

1. The first line contains two integers: T and N.
2. The second line contains \(N\) integers: \(V_1, V_2, \dots, V_N\) representing the coin values.
3. The third line contains \(N\) integers: \(C_1, C_2, \dots, C_N\) representing the number of coins of each type that Farmer John has.

Output Format:

Output a single integer representing the minimum total number of coins that change hands. If it is not possible to complete the transaction, output -1.

inputFormat

The input begins with a line containing two integers, T and N. The second line contains N space-separated integers representing the coin denominations \(V_1, V_2, \dots, V_N\). The third line contains N space-separated integers representing the number of coins \(C_1, C_2, \dots, C_N\) that Farmer John possesses.

outputFormat

Output a single integer indicating the minimum number of coins that change hands (coins used by John plus coins given as change). If there is no way to pay for the supplies while making exact change possible, output -1.

sample

6 2
5 1
1 3

2