DIY: Coin Change

Problem statement

You are given an integer total and a list of integers called coins. The variable coins holds a list of m coin denominations and total is the total amount of money.

You have to find the minimum number of coins that can make up the total amount by using any combination of the coins. If the amount can not be made up return -1. If the total amount is 0, return 0.

We may assume that we have an infinite number of each kind of coin.

Input

The first input will be a list of integers called coins, and the second input will be an integer called total. The following are example inputs:

Input 1:

coins = [1,2,5]
total = 11

Input 2:

coins = [2]
total = 4

Input 3:

coins = [5]
total = 3

Input 4:

coins = [1,2,5]
total = 0

Output

The output will be an integer that represents the total number of coins needed to make up the amount. The followings are sample outputs to the above inputs:

Output 1:

3

Output 2:

2

Output 3:

-1

Output 4:

0

Coding exercise

You need to implement the function CoinChange(coins, total) in the skeleton code below.