Given a value V and array coins[] of size M, the task is to make the change for V cents, given that you have an infinite supply of each of coins{coins_{1}, coins_{2}, ..., coins_{m}} valued coins. Find the minimum number of coins to make the change. If not possible to make change then return -1.
Example 1:
Input: V = 30, M = 3, coins[] = {25, 10, 5}
Output: 2
Explanation: Use one 25 cent coin
and one 5 cent coin
Example 2:
Input: V = 11, M = 4,coins[] = {9, 6, 5, 1} 
Output: 2 
Explanation: Use one 6 cent coin
and one 5 cent coin
Your Task:  
You don't need to read input or print anything. Complete the function minCoins() which takes V, M and array coins as input parameters and returns the answer.
Expected Time Complexity: O(V*M)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V*M ≤ 10^{6}
All array elements are distinct

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def minCoins(self, coins, M, V):
		# code here

Solutions:
class Solution:

	def minCoins(self, coins, M, V):
		(n, sm) = (M, V)
		arr = coins
		dp = [[float('inf') for i in range(sm + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, sm + 1):
				if j < arr[i - 1]:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = min(1 + dp[i][j - arr[i - 1]], dp[i - 1][j])
		return dp[n][sm] if dp[n][sm] != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		target = V
		table = [-1 for x in range(target + 1)]
		table[0] = 0
		for i in range(target + 1):
			if table[i] == -1:
				continue
			for j in range(len(coins)):
				if i + coins[j] <= target:
					if table[i + coins[j]] == -1 or table[i + coins[j]] > table[i] + 1:
						table[i + coins[j]] = table[i] + 1
		return table[target]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [1000000000.0] * (V + 1)
		dp[0] = 0
		for i in range(1, V + 1):
			for j in range(M):
				if i - coins[j] >= 0 and dp[i - coins[j]] != 1000000000.0:
					dp[i] = min(dp[i], 1 + dp[i - coins[j]])
		if dp[V] == 1000000000.0:
			return -1
		return dp[V]


class Solution:

	def minCoins(self, coins, M, V):
		dp = {}

		def solve(target):
			if target == 0:
				return 0
			if target < 0:
				return 1000000000.0
			if target in dp:
				return dp[target]
			mini = 1000000000.0
			for i in coins:
				ans = solve(target - i)
				if ans != 1000000000.0:
					mini = min(1 + ans, mini)
			dp[target] = mini
			return mini
		ans = solve(V)
		if ans == 1000000000.0:
			return -1
		return ans


class Solution:

	def minCoins(self, coins, m, V):
		dp = [float('inf')] * (V + 1)
		dp[0] = 0
		for i in range(m):
			for j in range(coins[i], V + 1):
				if dp[j - coins[i]] != float('inf'):
					dp[j] = min(dp[j], dp[j - coins[i]] + 1)
		if dp[V] == float('inf'):
			return -1
		return dp[V]


class Solution:

	def minCoins(self, coins, M, V):
		ans = [V + 1] * (V + 1)
		ans[0] = 0
		for i in range(1, V + 1):
			for coin in coins:
				if i - coin >= 0:
					ans[i] = min(ans[i], 1 + ans[i - coin])
		return -1 if ans[-1] == V + 1 else ans[-1]


class Solution:

	def helper(self, ind, coins, V, dp):
		if ind == len(coins) - 1:
			if V == 0 or (V > 0 and V % coins[ind] == 0):
				return V // coins[ind]
			else:
				return 1000000000.0
		if dp[ind][V] != -1:
			return dp[ind][V]
		(take, nottake) = (1000000000.0, 1000000000.0)
		if V >= coins[ind]:
			dp[ind][V] = min(1 + self.helper(ind, coins, V - coins[ind], dp), self.helper(ind + 1, coins, V, dp))
			return dp[ind][V]
		else:
			dp[ind][V] = self.helper(ind + 1, coins, V, dp)
			return dp[ind][V]

	def minCoins(self, coins, M, V):
		dp = [[-1 for j in range(V + 1)] for i in range(M + 1)]
		ans = self.helper(0, coins, V, dp)
		if ans == 1000000000.0:
			return -1
		else:
			return ans


class Solution:

	def minCoins(self, coins, M, V):
		dp = [99999 for i in range(V + 1)]
		dp[0] = 0
		for coin in coins:
			for rem_val in range(coin, V + 1):
				dp[rem_val] = min(dp[rem_val - coin] + 1, dp[rem_val])
		return -1 if dp[V] == 99999 else dp[V]


class Solution:

	def minCoins(self, num, M, a):
		dp = [0 for i in range(a + 1)]
		t = [0 for i in range(a + 1)]
		for i in range(a + 1):
			if i % num[0] == 0:
				dp[i] = i // num[0]
			else:
				dp[i] = 1000000000.0
		for i in range(1, len(num)):
			for j in range(a + 1):
				n = dp[j]
				ta = float('inf')
				if num[i] <= j:
					ta = 1 + t[j - num[i]]
				t[j] = min(n, ta)
			dp = t
		a = dp[a]
		if a != 1000000000.0:
			return a
		return -1


import sys

class Solution:

	def minCoins(self, coins, M, V):
		table = [0 for i in range(V + 1)]
		table[0] = 0
		for i in range(1, V + 1):
			table[i] = float('inf')
		for i in range(v + 1):
			for j in range(M):
				if coins[j] <= i:
					count = table[i - coins[j]]
					if count != float('inf') and count + 1 < table[i]:
						table[i] = count + 1
		if table[V] == float('inf'):
			return -1
		return table[v]


class Solution:

	def sol(self, coins, M, v, memo={}):
		if v == 0:
			return 0
		if v in memo:
			return memo[v]
		min_ = float('inf')
		for i in range(len(coins)):
			if v >= coins[i]:
				count = self.sol(coins, M, v - coins[i], memo)
				if count != -1 and count + 1 < min_:
					min_ = count + 1
		memo[v] = min_ if min_ != float('inf') else -1
		return memo[v]

	def minCoins(self, coins, M, v):
		ans = self.sol(coins, M, v, memo={})
		return ans


import sys

class Solution:

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M)]

		def countCoins(i, T):
			if i == 0:
				return T // coins[i] if T % coins[i] == 0 else 1000000007
			if dp[i][T] != -1:
				return dp[i][T]
			notpick = 0 + countCoins(i - 1, T)
			pick = 1 + countCoins(i, T - coins[i]) if T >= coins[i] else sys.maxsize
			dp[i][T] = min(pick, notpick)
			return dp[i][T]
		ans = countCoins(M - 1, V)
		return ans if ans < 1000000007 else -1


from sys import maxsize

class Solution:

	def minCoins(self, coins, M, V):

		def helper(coins, M, V, cache=dict()):
			if (V, M) in cache:
				return cache[V, M]
			if V == 0:
				return 0
			if V < 0 or M == 0:
				return maxsize
			ans1 = helper(coins, M, V - coins[M - 1], cache) + 1
			ans2 = helper(coins, M - 1, V, cache)
			ans = min(ans1, ans2)
			cache[V, M] = ans
			return ans
		coins.sort()
		ans = helper(coins, M, V)
		if ans >= maxsize:
			return -1
		return ans


class Solution:

	def minCoins(self, coins, M, V):
		dp = [float('inf')] * (V + 1)
		dp[0] = 0
		for i in range(1, len(dp)):
			for j in range(M):
				if V - coins[j] >= 0:
					dp[i] = min(dp[i], 1 + dp[i - coins[j]])
		return dp[V] if dp[V] != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		dp = [0] * (V + 1)

		def find(A):
			if A < 0:
				return 9999999999
			if A == 0:
				return 0
			if dp[A]:
				return dp[A]
			mincoins = 9999999999
			for coin in coins:
				if coin <= A:
					mincoins = min(mincoins, find(A - coin))
			dp[A] = 1 + mincoins
			return dp[A]
		ans = find(V)
		if ans >= 9999999999:
			return -1
		return ans


from sys import maxsize

class Solution:

	def solve(self, coins, target):
		if target < 0:
			return maxsize
		if target == 0:
			return 0
		mini = maxsize
		for coin in coins:
			ans = self.solve(coins, target - coin)
			if ans != maxsize:
				mini = min(mini, ans + 1)
		return mini

	def solve_memo(self, coins, target, F):
		if target < 0:
			return maxsize
		if target == 0:
			return 0
		if F[target] != -1:
			return F[target]
		mini = maxsize
		for coin in coins:
			ans = self.solve_memo(coins, target - coin, F)
			if ans != maxsize:
				mini = min(mini, ans + 1)
		F[target] = mini
		return F[target]

	def minCoins(self, coins, M, V):
		F = [-1] * (V + 1)
		ans = self.solve_memo(coins, V, F)
		return ans if ans != maxsize else -1


class Solution:

	def minCoins(self, coins, M, V):
		poss = [-1 for i in range(V + 1)]
		for val in coins:
			if val <= V:
				poss[val] = 1
				for j in range(V - val + 1):
					if poss[j] > 0:
						poss[j + val] = min(poss[j + val], poss[j] + 1) if poss[j + val] > 0 else poss[j] + 1
		return poss[V]


class Solution:

	def minCoins(self, coins, M, V):
		dp = []
		for i in range(V + 1):
			dp.append(100000.0)
		dp[0] = 0
		for i in range(1, V + 1):
			for j in range(M):
				if coins[j] <= i:
					res = dp[i - coins[j]]
					if res + 1 < dp[i]:
						dp[i] = res + 1
		if dp[v] == 100000.0:
			return -1
		return dp[v]


from functools import lru_cache

class Solution:

	def minCoins(self, coins, M, V):

		@lru_cache(maxsize=None)
		def findCount(val):
			if val == 0:
				return 0
			if val < 0:
				return float('inf')
			cur_count = float('inf')
			for coin in coins:
				cur_count = min(cur_count, findCount(val - coin))
			return 1 + cur_count
		rs = findCount(V)
		return rs if rs < float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		dp = [0] * (V + 1)
		coins.sort(reverse=True)
		for coin in coins:
			if coin <= V:
				dp[coin] = 1
			for i in range(coin, V + 1):
				if dp[i] != 0:
					if i + coin > V:
						break
					elif dp[i + coin] == 0:
						dp[i + coin] = dp[i] + 1
					else:
						dp[i + coin] = min(dp[i] + 1, dp[i + coin])
		return dp[V] if dp[V] != 0 else -1


class Solution:

	def f(self, ind, target, arr, dp):
		if ind == 0:
			if target % arr[0] == 0:
				return target // arr[0]
			else:
				return 1000000000.0
		if dp[ind][target] != -1:
			return dp[ind][target]
		ntake = 0 + self.f(ind - 1, target, arr, dp)
		take = 1000000000.0
		if arr[ind] <= target:
			take = 1 + self.f(ind, target - arr[ind], arr, dp)
		dp[ind][target] = min(take, ntake)
		return dp[ind][target]

	def minCoins(self, coins, M, V):
		dp = [[1000000000.0 for i in range(V + 1)] for i in range(M)]
		for target in range(V + 1):
			if target % coins[0] == 0:
				dp[0][target] = target // coins[0]
		for ind in range(1, M):
			for target in range(V + 1):
				ntake = 0 + dp[ind - 1][target]
				take = 1000000000.0
				if coins[ind] <= target:
					take = 1 + dp[ind][target - coins[ind]]
				dp[ind][target] = min(take, ntake)
		if dp[M - 1][V] >= 1000000000.0:
			return -1
		return dp[M - 1][V]


class Solution:

	def solve(self, coins, M, V, dp):
		if V == 0:
			return 0
		if V < 0:
			return float('inf')
		if dp[V] != -1:
			return dp[V]
		mini = float('inf')
		for i in range(len(coins)):
			ans = self.solve(coins, M, V - coins[i], dp)
			if ans != float('inf'):
				mini = min(mini, 1 + ans)
		dp[V] = mini
		return dp[V]

	def minCoins(self, coins, M, V):
		dp = [-1 for i in range(V + 1)]
		ans = self.solve(coins, M, V, dp)
		if ans == float('inf'):
			return -1
		else:
			return ans


class Solution:

	def helper(self, A, V):
		key = V
		if self.d.get(key) is not None:
			return self.d[key]
		if V == 0:
			return 0
		if V < 0:
			return 10 ** 9
		ans = 10 ** 9
		for i in range(len(A)):
			ans = min(ans, 1 + self.helper(A, V - A[i]))
		self.d[key] = ans
		return ans

	def minCoins(self, coins, M, V):
		self.d = {}
		ans = self.helper(coins, V)
		if ans == 10 ** 9:
			return -1
		return ans


class Solution:

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M)]

		def helper(idx, V):
			if idx == 0:
				if V % coins[0] == 0:
					return V // coins[0]
				else:
					return float('inf')
			if dp[idx][V] != -1:
				return dp[idx][V]
			not_take = helper(idx - 1, V)
			take = float('inf')
			if V >= coins[idx]:
				take = 1 + helper(idx, V - coins[idx])
			dp[idx][V] = min(take, not_take)
			return dp[idx][V]
		if helper(M - 1, V) == float('inf'):
			return -1
		return helper(M - 1, V)


class Solution:

	def minCoins(self, coins, M, amount):

		def f(coins, amt):
			if amt == 0:
				return 0
			if amt < 0:
				return float('inf')
			if amt in memo:
				return memo[amt]
			ans = float('inf')
			for i in range(n):
				ans = min(ans, 1 + f(coins, amt - coins[i]))
			memo[amt] = ans
			return memo[amt]
		if amount == 0:
			return 0
		ans = float('inf')
		n = len(coins)
		memo = {}
		for i in range(n):
			ans = min(ans, 1 + f(coins, amount - coins[i]))
		return ans if ans != float('inf') else -1


class Solution:

	def fun(self, idx, arr, target, dp):
		if idx == 0:
			if target % arr[0] == 0:
				return target // arr[0]
			else:
				return float('inf')
		if dp[idx][target] != -1:
			return dp[idx][target]
		np = 0 + self.fun(idx - 1, arr, target, dp)
		p = float('inf')
		if arr[idx] <= target:
			p = 1 + self.fun(idx, arr, target - arr[idx], dp)
		dp[idx][target] = min(p, np)
		return dp[idx][target]

	def minCoins(self, arr, n, target):
		dp = [[0 for i in range(target + 1)] for j in range(n)]
		for i in range(target + 1):
			if i % arr[0] == 0:
				dp[0][i] = i // arr[0]
			else:
				dp[0][i] = float('inf')
		for i in range(1, n):
			for t in range(target + 1):
				np = 0 + dp[i - 1][t]
				p = float('inf')
				if arr[i] <= t:
					p = 1 + dp[i][t - arr[i]]
				dp[i][t] = min(p, np)
		if dp[n - 1][target] == float('inf'):
			return -1
		else:
			return dp[n - 1][target]


class Solution:

	def minCoins(self, coins, M, V):
		l = [float('inf') for _ in range(V + 1)]
		l[0] = 0
		for coin in coins:
			for i in range(coin, V + 1):
				l[i] = min(l[i], 1 + l[i - coin])
		if l[-1] == float('inf'):
			return -1
		return l[-1]


import sys

class Solution:

	def minCoins(self, coins, M, V):
		table = [sys.maxsize for i in range(V + 1)]
		table[0] = 0
		for i in range(1, V + 1):
			for j in range(M):
				if coins[j] <= i:
					sub_res = table[i - coins[j]]
					if sub_res != sys.maxsize and sub_res + 1 < table[i]:
						table[i] = sub_res + 1
		if table[V] == sys.maxsize:
			return -1
		return table[V]


import sys

class Solution:

	def minCoins(self, coins, M, V):
		t = [[0 for j in range(V + 1)] for i in range(M + 1)]
		max = 999998
		for i in range(V + 1):
			if i == 0:
				t[0][i] = 999998
		for j in range(1, V + 1):
			if j % coins[0] == 0:
				t[1][j] = int(j / coins[0])
			else:
				t[1][j] = 999998
		for i in range(2, M + 1):
			for j in range(1, V + 1):
				if coins[i - 1] <= j:
					t[i][j] = min(1 + t[i][j - coins[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[M][V] == 999998:
			return -1
		return t[M][V]


class Solution:

	def minCoins(self, coins, M, Sum):
		dp = [float('inf')] * (Sum + 1)
		dp[0] = 0
		for a in range(1, Sum + 1):
			for c in coins:
				if a - c >= 0:
					dp[a] = min(dp[a], 1 + dp[a - c])
		return dp[Sum] if dp[Sum] != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		self.maxx = 99999999
		dp = [self.maxx] * (V + 1)
		dp[0] = 0
		for i in range(1, V + 1):
			for j in range(M):
				if i < coins[j]:
					continue
				dp[i] = min(dp[i], 1 + dp[i - coins[j]])
		if dp[-1] == self.maxx:
			return -1
		return dp[-1]


from sys import maxsize

class Solution:

	def solve(self, coins, target):
		if target < 0:
			return maxsize
		if target == 0:
			return 0
		mini = maxsize
		for c in coins:
			ans = self.solve(coins, target - c)
			if ans != maxsize:
				mini = min(mini, ans + 1)
		return mini

	def solve_memo(self, coins, target, F):
		if target < 0:
			return maxsize
		if target == 0:
			F[0] = 0
			return F[0]
		if F[target] != maxsize:
			return F[target]
		mini = maxsize
		for c in coins:
			ans = self.solve_memo(coins, target - c, F)
			if ans != maxsize:
				mini = min(mini, ans + 1)
		F[target] = mini
		return F[target]

	def solve_tab(self, coins, M, V):
		F = [maxsize] * (V + 1)
		F[0] = 0
		for i in range(1, V + 1):
			for c in coins:
				if i - c >= 0 and F[i - c] != maxsize:
					F[i] = min(F[i], F[i - c] + 1)
		return F[V]

	def minCoins(self, coins, M, V):
		ans = self.solve_tab(coins, M, V)
		return ans if ans != maxsize else -1


class Solution:

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M + 1)]
		self.dfs(coins, M, V, dp)
		return -1 if dp[-1][-1] == float('inf') else dp[-1][-1]

	def dfs(self, coins, N, target, dp):
		if target == 0:
			return 0
		elif N == 0:
			return float('inf')
		elif dp[N][target] != -1:
			return dp[N][target]
		if coins[N - 1] <= target:
			dp[N][target] = min(1 + self.dfs(coins, N, target - coins[N - 1], dp), self.dfs(coins, N - 1, target, dp))
		else:
			dp[N][target] = self.dfs(coins, N - 1, target, dp)
		return dp[N][target]


class Solution:

	def minCoins(self, coins, M, V):
		import sys
		dp = [sys.maxsize for i in range(V + 1)]
		dp[0] = 0
		for i in range(1, V + 1):
			for j in range(M):
				if coins[j] <= i:
					sub = dp[i - coins[j]]
					if sub != sys.maxsize and sub + 1 < dp[i]:
						dp[i] = dp[i - coins[j]] + 1
		if dp[V] == sys.maxsize:
			return -1
		return dp[V]


class Solution:

	def minCoins(self, coins, M, V):
		coins.sort()
		dp = [float('inf') for _ in range(V + 1)]
		for coin in coins:
			j = 0
			while j * coin <= V:
				dp[j * coin] = j
				j += 1
		for v in range(1, V + 1):
			for coin in coins:
				if coin >= v:
					break
				dp[v] = min(dp[v], dp[v - coin] + 1)
		return -1 if dp[-1] == float('inf') else dp[-1]


class Solution:

	def minCoins(self, coins, M, V):
		dp = []
		dp.append(0)
		for i in range(1, V + 1):
			arr = []
			for j in range(M):
				k = i - coins[j]
				if k > 0:
					arr.append(1 + dp[k])
				elif k == 0:
					arr.append(1)
			if arr == []:
				dp.append(V + 1)
			else:
				dp.append(min(arr))
		if dp[V] <= V:
			return dp[V]
		return -1


class Solution:

	def minCoins(self, coins, M, V):
		mod = float('inf')
		t = [[-1 for _ in range(V + 1)] for _ in range(M + 1)]
		for i in range(1, M + 1):
			t[i][0] = 0

		def solve(coins, n, m):
			if m == 0:
				return 1000000000.0
			if v == 0:
				return 0
			if t[m][n] != -1:
				return t[m][n]
			if coins[m - 1] <= n:
				t[m][n] = min(1 + solve(coins, n - coins[m - 1], m), solve(coins, n, m - 1))
				return t[m][n]
			else:
				t[m][n] = solve(coins, n, m - 1)
				return t[m][n]
		ans = solve(coins, V, M)
		if ans == 1000000000.0:
			return -1
		return ans


class Solution:

	def minCoins(self, coins, m, v):
		coins.sort()
		coins = coins[::-1]
		dp = [[10 ** 6 for _ in range(v + 1)] for _ in range(m + 1)]
		for i in range(m + 1):
			dp[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, v + 1):
				if j % coins[i - 1] == 0:
					dp[i][j] = j // coins[i - 1]
		for i in range(1, m + 1):
			for j in range(coins[i - 1], v + 1):
				dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + dp[i][coins[i - 1]], dp[i][j])
		if dp[m][v] == 10 ** 6:
			return -1
		return dp[m][v]


class Solution:

	def minCoins(self, coins, M, V):
		n = len(coins)
		dp = [[0 for _ in range(V + 1)] for i in range(M + 1)]

		def func(n, amount):
			for i in range(n + 1):
				for j in range(amount + 1):
					if i == 0:
						dp[i][j] = 100000
					if j == 0:
						dp[i][j] = 0
			for i in range(1, n + 1):
				for j in range(1, amount + 1):
					if coins[i - 1] > j:
						dp[i][j] = dp[i - 1][j]
					else:
						dp[i][j] = min(1 + dp[i][j - coins[i - 1]], dp[i - 1][j])
		func(M, V)
		if dp[M][V] >= 100000:
			return -1
		return dp[M][V]


import math

class Solution:

	def minCoins(self, coins, M, V):

		def coinChange(coins, amount):
			dp = [math.inf] * (amount + 1)
			dp[0] = 0
			for coin in coins:
				for i in range(coin, amount + 1):
					if i - coin >= 0:
						dp[i] = min(dp[i], dp[i - coin] + 1)
			return -1 if dp[-1] == math.inf else dp[-1]
		return coinChange(coins, V)


class Solution:

	def minCoins(self, coins, M, V):

		def solve(coins, v, dp):
			if v == 0:
				return 0
			if v < 0:
				return 999
			mi = 1000
			if dp[v] != -1:
				return dp[v]
			for i in range(len(coins)):
				mi = min(mi, solve(coins, v - coins[i], dp) + 1)
			dp[v] = mi
			return dp[v]
		dp = [-1 for i in range(V + 1)]
		ans = solve(coins, V, dp)
		return ans if ans != 1000 else -1


class Solution:

	def fun(self, coins, ind, target, dp):
		if ind == 0:
			if target % coins[0] == 0:
				return target // coins[0]
			return 1000000000.0
		if dp[ind][target] != -1:
			return dp[ind][target]
		not_take = self.fun(coins, ind - 1, target, dp)
		take = 1000000000.0
		if target >= coins[ind]:
			take = 1 + self.fun(coins, ind, target - coins[ind], dp)
		dp[ind][target] = min(take, not_take)
		return dp[ind][target]

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M + 1)]
		ans = self.fun(coins, M - 1, V, dp)
		if ans != 1000000000.0:
			return ans
		return -1


class Solution:

	def minCoins(self, coins, N, amount):
		mod = int(100000000.0)
		dp = [[mod for i in range(amount + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			for j in range(amount + 1):
				if j == 0:
					dp[i][j] = 0
		for j in range(1, amount + 1):
			if j % coins[0] == 0:
				dp[1][j] = j // coins[0]
		for i in range(N + 1):
			for j in range(amount + 1):
				if coins[i - 1] <= j:
					dp[i][j] = min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[N][amount] == mod:
			return -1
		return dp[N][amount]


class Solution:

	def minCoins(self, coins, M, V):
		return coinChange(coins, V, M)

def coinChange(wt, W, n):
	dp = [[0 for i in range(W + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(W + 1):
			if i == 0:
				dp[i][j] = 100000009
			if j == 0:
				dp[i][j] = 0
	for i in range(1, n + 1):
		for j in range(1, W + 1):
			if wt[i - 1] <= j:
				dp[i][j] = min(1 + dp[i][j - wt[i - 1]], dp[i - 1][j])
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[n][W] if dp[n][W] != 100000009 else -1


import sys

class Solution:

	def minCoins(self, coins, M, V):

		def solve(V, dp):
			if V == 0:
				return dp[0]
			if dp[V] != -1:
				return dp[V]
			mx = sys.maxsize
			for i in coins:
				if V - i < 0:
					continue
				else:
					m = solve(V - i, dp)
					if m + 1 < mx and m != sys.maxsize:
						mx = m + 1
			dp[V] = mx
			return dp[V]
		dp = [-1] * (V + 1)
		dp[0] = 0
		ans = solve(V, dp)
		if ans == sys.maxsize:
			return -1
		return ans


class Solution:

	def solve(self, coins, M, V, dp):
		if V == 0:
			return 0
		if V < 0:
			return 999
		mi = 999
		if dp[V] != -1:
			return dp[V]
		for i in range(M):
			mi = min(mi, self.solve(coins, M, V - coins[i], dp) + 1)
		dp[V] = mi
		return dp[V]

	def minCoins(self, coins, M, V):
		dp = [-1 for i in range(V + 1)]
		ans = self.solve(coins, M, V, dp)
		if ans == 999:
			return -1
		return ans


class Solution:

	def minCoins(self, coins, M, V):
		cache = {}

		def dfs(left):
			if left < 0:
				return float('inf')
			if left == 0:
				return 0
			if left in cache:
				return cache[left]
			cache[left] = float('inf')
			for c in coins:
				cache[left] = min(cache[left], 1 + dfs(left - c))
			return cache[left]
		res = dfs(V)
		return res if res != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		n = len(coins)
		dp = [float('inf') for _ in range(V + 1)]
		dp[V] = 0
		for i in range(V - 1, -1, -1):
			for coin in coins:
				if i + coin <= V:
					dp[i] = min(dp[i], dp[i + coin] + 1)
		return dp[0] if dp[0] != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, V):
		mod = float('inf')
		t = [[mod for _ in range(V + 1)] for _ in range(M + 1)]
		for i in range(1, M + 1):
			t[i][0] = 0
		for j in range(1, V + 1):
			if j % coins[0] == 0:
				t[1][j] = j // coins[0]
		for i in range(1, M + 1):
			for j in range(1, V + 1):
				if coins[i - 1] <= j:
					t[i][j] = min(t[i][j - coins[i - 1]] + 1, t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[M][V] == mod:
			return -1
		return t[M][V]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [V + 1 for i in range(V + 1)]
		dp[0] = 0
		for i in range(V + 1):
			for coin in coins:
				if i - coin == 0:
					dp[i] = 1
					break
				elif i - coin > 0:
					dp[i] = min(dp[i], dp[i - coin] + 1)
		if dp[V] == V + 1:
			return -1
		return dp[V]


from sys import maxsize

class Solution:

	def minCoins(self, coins, M, V):
		memo = [-maxsize] * (V + 1)

		def dp(target):
			nonlocal memo
			if memo[target] != -maxsize:
				return memo[target]
			if target < 0:
				return maxsize
			if target == 0:
				return 0
			ans = maxsize
			for x in coins:
				if x <= target:
					ret = dp(target - x)
					if ret < maxsize:
						ans = min(ans, 1 + ret)
			memo[target] = ans
			return memo[target]
		ans = dp(V)
		return -1 if ans == maxsize else ans


class Solution:

	def minCoins(self, a, m, v):
		dp = [v + 2] * (v + 1)
		dp[0] = 0
		for i in range(1, v + 1):
			minVal = v + 2
			for j in range(m):
				if i - a[j] >= 0:
					minVal = min(minVal, dp[i - a[j]] + 1)
			dp[i] = minVal
		if dp[v] > v + 1:
			return -1
		return dp[v]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [V + 1 for i in range(V + 1)]
		dp[0] = 0
		for i in range(1, len(dp)):
			for c in coins:
				if i - c >= 0:
					dp[i] = min(dp[i], 1 + dp[i - c])
		if dp[-1] == V + 1:
			return -1
		return dp[-1]


class Solution:

	def minCoins(self, coins, M, amount):
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			for i in range(coin, amount + 1):
				dp[i] = min(dp[i], dp[i - coin] + 1)
		return dp[amount] if dp[amount] != float('inf') else -1


class Solution:

	def minCoins(self, coins, M, amount):
		(m, n) = (len(coins), amount)
		dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
		for j in range(1, n + 1):
			dp[0][j] = float('inf')
		for i in range(m + 1):
			dp[i][0] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				coin = coins[i - 1]
				if coin <= j:
					dp[i][j] = min(1 + dp[i][j - coin], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[m][n] == float('inf'):
			return -1
		return dp[m][n]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M + 1)]
		for i in range(M + 1):
			dp[i][0] = 0
		for i in range(1, M + 1):
			for j in range(1, V + 1):
				if coins[i - 1] <= j:
					ab = dp[i - 1][j]
					le = dp[i][j - coins[i - 1]]
					if ab != -1 and le != -1:
						dp[i][j] = min(1 + le, ab)
					elif ab == -1 and le != -1:
						dp[i][j] = 1 + le
					elif ab != -1 and le == -1:
						dp[i][j] = ab
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def minCoins(self, coins, M, V):
		max_int = 1000000
		t = [[-1] * (V + 1) for i in range(M + 1)]
		for i in range(M + 1):
			for j in range(V + 1):
				if i == 0 and j >= 0:
					t[i][j] = max_int
				if j == 0 and i > 0:
					t[i][j] = 0
				if i == 1 and j > 0:
					if j % coins[i - 1] == 0:
						t[i][j] = j // coins[i - 1]
					else:
						t[i][j] = max_int
		for i in range(2, M + 1):
			for j in range(1, V + 1):
				if coins[i - 1] <= j:
					t[i][j] = min(1 + t[i][j - coins[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[M][V] == max_int or t[M][V] == max_int + 1:
			return -1
		return t[M][V]


import math

class Solution:

	def minCoins(self, coins, M, V):
		dp = [math.inf for _ in range(V + 1)]
		dp[0] = 0
		for i in range(len(coins)):
			c = coins[i]
			for j in range(1, V + 1):
				if j >= c:
					dp[j] = min(dp[j - c] + 1, dp[j])
		if dp[-1] == math.inf:
			return -1
		return dp[-1]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [V + 1] * (V + 1)
		dp[0] = 0
		for a in range(1, V + 1):
			for c in coins:
				if a - c >= 0:
					dp[a] = min(dp[a], 1 + dp[a - c])
		return dp[V] if dp[v] != V + 1 else -1


class Solution:

	def fun(self, idx, arr, target, dp):
		if idx == 0:
			if target % arr[0] == 0:
				return target // arr[0]
			else:
				return float('inf')
		if dp[idx][target] != -1:
			return dp[idx][target]
		np = 0 + self.fun(idx - 1, arr, target, dp)
		p = float('inf')
		if arr[idx] <= target:
			p = 1 + self.fun(idx, arr, target - arr[idx], dp)
		dp[idx][target] = min(p, np)
		return dp[idx][target]

	def minCoins(self, arr, n, T):
		dp = [[0 for _ in range(T + 1)] for _ in range(n)]
		for i in range(T + 1):
			if i % arr[0] == 0:
				dp[0][i] = i // arr[0]
			else:
				dp[0][i] = int(1000000000.0)
		for ind in range(1, n):
			for target in range(T + 1):
				notTake = 0 + dp[ind - 1][target]
				take = int(1000000000.0)
				if arr[ind] <= target:
					take = 1 + dp[ind][target - arr[ind]]
				dp[ind][target] = min(notTake, take)
		ans = dp[n - 1][T]
		if ans >= int(1000000000.0):
			return -1
		return ans


import sys

class Solution:

	def minCoins(self, coins, M, V):

		def inf(ind, s, a, dp):
			if ind == 0:
				if s % a[ind] == 0:
					return s // a[ind]
				else:
					return sys.maxsize
			if dp[ind][s] != -1:
				return dp[ind][s]
			nt = 0 + inf(ind - 1, s, a, dp)
			t = sys.maxsize
			if s >= a[ind]:
				t = 1 + inf(ind, s - a[ind], a, dp)
			dp[ind][s] = min(t, nt)
			return dp[ind][s]
		dp = [[-1 for i in range(V + 1)] for j in range(M)]
		z = inf(M - 1, V, coins, dp)
		if z >= sys.maxsize:
			return -1
		return z


import math

class Solution:

	def minCoins(self, coins, M, V):
		d = [[-1 for i in range(V + 1)] for j in range(M + 1)]

		def dfs(i, V):
			if V < 0:
				return math.inf
			if V == 0:
				return 0
			if i == M:
				if V > 0:
					return math.inf
				return 0
			if d[i][V] != -1:
				return d[i][V]
			d[i][V] = min(1 + dfs(i, V - coins[i]), dfs(i + 1, V))
			return d[i][V]
		a = dfs(0, V)
		if a == math.inf:
			return -1
		return a


import sys

class Solution:

	def minCoins(self, coins, M, V):
		dp = [-1] * (V + 1)
		ans = self.helper_memo(coins, V, dp)
		if ans == sys.maxsize:
			return -1
		else:
			return ans

	def helper_memo(self, coins, V, dp):
		if V == 0:
			return 0
		if V < 0:
			return sys.maxsize
		if dp[V] != -1:
			return dp[V]
		min_coins = sys.maxsize
		for coin in coins:
			ans = self.helper_memo(coins, V - coin, dp)
			if ans != sys.maxsize:
				min_coins = min(min_coins, 1 + ans)
		dp[V] = min_coins
		return dp[V]


class Solution:

	def minCoins(self, coins, M, V):
		d = [-1 for i in range(V + 1)]
		for c in coins:
			if c <= V:
				d[c] = 1
		for i in range(V + 1):
			if d[i] == -1:
				r = 1000000000.0
				for c in coins:
					if i - c >= 0 and d[i - c] != -1:
						if 1 + d[i - c] < r:
							r = 1 + d[i - c]
				if r != 1000000000.0:
					d[i] = r
		return d[V]


import sys

class Solution:

	def minCoins(self, coins, n, amount):
		un_K = [[0 for i in range(amount + 1)] for i in range(n + 1)]
		for i in range(amount + 1):
			un_K[0][i] = sys.maxsize - 1
		for i in range(n + 1):
			un_K[i][0] = 0
		for i in range(1, amount + 1):
			if i % coins[0] != 0:
				un_K[1][i] = sys.maxsize - 1
			else:
				un_K[1][i] = i // coins[0]
		for i in range(1, n + 1):
			for j in range(1, amount + 1):
				if coins[i - 1] <= j:
					un_K[i][j] = min(1 + un_K[i][j - coins[i - 1]], un_K[i - 1][j])
				else:
					un_K[i][j] = un_K[i - 1][j]
		if un_K[n][amount] == sys.maxsize - 1:
			return -1
		return un_K[n][amount]


class Solution:

	def minCoins(self, coins, M, V):
		dp = [[-1 for i in range(V + 1)] for j in range(M)]
		ans = self.helper(M - 1, V, coins, dp)
		if ans < 10 ** 7:
			return ans
		return -1

	def helper(self, ind, T, coins, dp):
		if ind == 0:
			if T % coins[0] == 0:
				return T // coins[0]
			return 10 ** 7
		if dp[ind][T] != -1:
			return dp[ind][T]
		nottake = 0 + self.helper(ind - 1, T, coins, dp)
		take = 10 ** 7 + 1
		if coins[ind] <= T:
			take = 1 + self.helper(ind, T - coins[ind], coins, dp)
		dp[ind][T] = min(take, nottake)
		return dp[ind][T]


class Solution:

	def minCoins(self, coins, n, amount):
		dp = [[-1 for _ in range(amount + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(amount + 1):
			dp[0][j] = float('inf')
		for i in range(1, n + 1):
			for j in range(1, amount + 1):
				if coins[i - 1] <= j:
					dp[i][j] = min(1 + dp[i][j - coins[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][amount] if dp[n][amount] != float('inf') else -1