The Fewest Coins

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods so that the smallest number of coins changes hands; that is, the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him determine what this minimum number is.

Farmer John wants to buy $T$ cents of supplies ($1 \le T \le 10{,}000$). The currency system has $N$ ($1 \le N \le 100$) different coins, with values $V_1, V_2, \dots, V_N$ ($1 \le V_i \le 120$). Farmer John is carrying $C_1$ coins of value $V_1$, $C_2$ coins of value $V_2$, $\dots$, and $C_N$ coins of value $V_N$ ($0 \le C_i \le 10{,}000$). The shopkeeper has an unlimited supply of every coin and always makes change in the most efficient manner (using the fewest coins). Farmer John must, however, pay in a way that makes it possible to give exact change.

• Line 1: Two space-separated integers, $N$ and $T$.
• Line 2: $N$ space-separated integers, $V_1, V_2, \dots, V_N$ (the coin values).
• Line 3: $N$ space-separated integers, $C_1, C_2, \dots, C_N$ (how many of each coin Farmer John holds).

• Line 1: A single integer, the minimum number of coins involved in the payment and the change. If it is impossible for Farmer John to pay and receive exact change, output $-1$.

When $T = 70$, Farmer John pays 75 cents using a 50-cent coin and a 25-cent coin, and receives a 5-cent coin in change, for a total of 3 coins used in the transaction.