The Fewest Coins

Time limit1sMemory limit128 MB

Summary

Given coin denominations, bounded supplies that John holds, and unlimited shopkeeper change, find the minimum total number of coins exchanged so John pays at least T with exact change returned.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting, Brute force
Solved: No attempts yet

Problem

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.

Input

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).

Output

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$ .

Hint

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.

Examples5

Example 1
Input
```
3 70
5 25 50
5 2 1
```
Expected output
```
3
```
Example 2
Input
```
1 5
1
100
```
Expected output
```
5
```
Example 3
Input
```
1 3
5
1
```
Expected output
```
-1
```
Example 4
Input
```
3 75
5 25 50
5 2 1
```
Expected output
```
2
```
Example 5
Input
```
2 4
1 5
3 2
```
Expected output
```
2
```