You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
 
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0

Example 4:
Input: coins = [1], amount = 1
Output: 1

Example 5:
Input: coins = [1], amount = 2
Output: 2

 
Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Graph traversal

Starter code: class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        

Solutions:
class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		(n, res) = (len(coins), amount + 1)

		def dfs(index, target, cnt):
			nonlocal res
			if cnt + (target + coins[index] - 1) // coins[index] >= res:
				return
			if target % coins[index] == 0:
				res = cnt + target // coins[index]
				return
			if index == n - 1:
				return
			for i in range(target // coins[index], -1, -1):
				dfs(index + 1, target - coins[index] * i, cnt + i)
		dfs(0, amount, 0)
		return -1 if res > amount else res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount < 0:
			return -1
		elif amount == 0:
			return 0
		coins.sort(reverse=True)
		visited = set()
		q = collections.deque([])
		for c in coins:
			if c == amount:
				return 1
			elif c < amount:
				q.append(c)
				visited.add(c)
		count = 1
		while q:
			size = len(q)
			count += 1
			for _ in range(size):
				prev = q.popleft()
				for c in coins:
					cur = prev + c
					if cur == amount:
						return count
					elif cur < amount and cur not in visited:
						visited.add(cur)
						q.append(cur)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		INVALID = 2 ** 32
		dp = [INVALID] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			for i in range(coin, amount + 1):
				if dp[i - coin] >= dp[i]:
					continue
				dp[i] = dp[i - coin] + 1
		return -1 if dp[amount] == INVALID else dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		queue = [[amount, 0]]
		visited = {amount}
		for q in queue:
			for c in coins:
				if q[0] - c in visited:
					continue
				if q[0] == c:
					return q[1] + 1
				if q[0] > c:
					visited.add(q[0] - c)
					queue.append([q[0] - c, q[1] + 1])
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		queue = deque([(0, 0)])
		visited = [True] + [False] * amount
		while queue:
			(totalCoins, currVal) = queue.popleft()
			totalCoins += 1
			for coin in coins:
				nextVal = currVal + coin
				if nextVal == amount:
					return totalCoins
				if nextVal < amount:
					if not visited[nextVal]:
						visited[nextVal] = True
						queue.append((totalCoins, nextVal))
		return -1


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if not coins:
			return -1
		queue = deque([])
		for coin in coins:
			if amount - coin >= 0:
				queue.append((1, amount - coin))
		seen = set()
		while queue:
			nex = queue.popleft()
			if nex[1] == 0:
				return nex[0]
			for coin in coins:
				if nex[1] - coin not in seen and nex[1] - coin >= 0:
					queue.append((nex[0] + 1, nex[1] - coin))
					seen.add(nex[1] - coin)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			for a in range(coin, amount + 1):
				if dp[a - coin] >= dp[a]:
					continue
				dp[a] = dp[a - coin] + 1
		return dp[amount] if dp[amount] < float('inf') else -1


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		queue = deque()
		visited = set()
		queue.append((amount, 0))
		answer = -1
		while queue:
			(target, numCoins) = queue.popleft()
			if target == 0:
				answer = numCoins
				break
			elif target > 0:
				for coin in coins:
					if target - coin not in visited:
						visited.add(target - coin)
						queue.append((target - coin, numCoins + 1))
		return answer


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		res = 0
		queue = collections.deque([(amount, 0)])
		seen = {amount}
		while queue:
			(head, res) = queue.popleft()
			if head == 0:
				return res
			for c in coins:
				new_amount = head - c
				if new_amount > -1 and new_amount not in seen:
					queue.append((new_amount, res + 1))
					seen.add(new_amount)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount < 0:
			return -1
		if amount == 0:
			return 0
		q = [(amount, 0)]
		visited = {0}
		coins.sort(reverse=True)
		while q:
			(node, depth) = q.pop(0)
			for coin in coins:
				rest = node - coin
				if rest == 0:
					return depth + 1
				if rest > 0 and rest not in visited:
					q.append((rest, depth + 1))
					visited.add(rest)
		return -1


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		visited = {0}
		tempQueue = deque()
		tempQueue.append((0, 0))
		while tempQueue:
			(currentVal, currentCount) = tempQueue.popleft()
			for coin in coins:
				nextVal = currentVal + coin
				if nextVal == amount:
					return currentCount + 1
				elif nextVal < amount:
					if nextVal not in visited:
						visited.add(nextVal)
						tempQueue.append((nextVal, currentCount + 1))
		return -1


class Solution:

	def coinChange(self, coins, amount):
		coins.sort(reverse=True)
		queue = [(amount, 0)]
		visited = [False for i in range(amount + 1)]
		for (val, cnt) in queue:
			if val == 0:
				return cnt
			for coin in coins:
				if val - coin >= 0 and (not visited[val - coin]):
					visited[val - coin] = True
					queue.append((val - coin, cnt + 1))
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		queue = deque([])
		seen = set()
		coins = sorted(coins, reverse=True)
		queue.append((0, 0))
		while queue:
			(summ, num_coins) = queue.popleft()
			if summ == amount:
				return num_coins
			for coin in coins:
				if summ + coin <= amount and summ + coin not in seen:
					queue.append((summ + coin, num_coins + 1))
					seen.add(summ + coin)
		return -1


class Solution:

	def coinChange(self, coins, amount):
		if not coins:
			return -1
		if not amount:
			return 0
		if amount in coins:
			return 1
		C = tuple(sorted(coins, reverse=True))
		(length, self.ans) = (len(C) - 1, float('inf'))

		def find(coin, step, target):
			now_coin = C[coin]
			(q, r) = divmod(target, now_coin)
			if not r:
				self.ans = min(self.ans, step + q)
			elif coin < length and step + q + 1 < self.ans:
				coin += 1
				for j in range(q, -1, -1):
					find(coin, step + j, target - j * now_coin)
		find(0, 0, amount)
		return -1 if self.ans == float('inf') else self.ans


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			min = math.inf
			for j in coins:
				if i - j >= 0 and dp[i - j] < min:
					min = dp[i - j]
			dp[i] = min + 1
		return dp[-1] if dp[-1] != math.inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		numpath = [0] + [float('inf')] * amount
		for coin in coins:
			for i in range(coin, amount + 1):
				if numpath[i] > 1 + numpath[i - coin]:
					numpath[i] = 1 + numpath[i - coin]
		return numpath[amount] if numpath[amount] != float('inf') else -1


class Solution:
	from collections import deque

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount <= 0:
			return 0
		coins = set(coins)
		count = 1
		q = deque()
		q.append((amount, count))
		visited = set()
		visited.add(amount)
		while q:
			(remain, count) = q.popleft()
			if remain in coins:
				return count
			for c in coins:
				if remain - c > 0 and remain - c not in visited:
					q.append((remain - c, count + 1))
					visited.add(remain - c)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def bfs():
			q = [(amount, 0)]
			if amount == 0:
				return 0
			seen = set()
			coins.sort(reverse=True)
			print(coins)
			while len(q) > 0:
				(a, ci) = q.pop(0)
				if a in seen:
					continue
				else:
					seen.add(a)
				for c in coins:
					if a - c == 0:
						return ci + 1
					if a - c > 0:
						q.append((a - c, ci + 1))
			return -1

		def dfs():
			if amount == 0:
				return 0
			coins.sort()
			s = [(amount, 0)]
			while len(s) > 0:
				(a, ci) = s.pop()
				for c in coins:
					if a - c == 0:
						return ci + 1
					if a - c > 0:
						s.append((a - c, ci + 1))
			return -1

		def paste() -> int:
			queue = deque([])
			seen = set()
			queue.append((0, 0))
			while queue:
				(summ, num_coins) = queue.popleft()
				if summ == amount:
					return num_coins
				for coin in coins:
					if summ + coin <= amount and summ + coin not in seen:
						queue.append((summ + coin, num_coins + 1))
						seen.add(summ + coin)
			return -1
		return paste()


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		Visited = {amount: 0}
		coins.sort(reverse=True)
		queue = deque()
		queue.append(amount)
		while queue:
			curr = queue.popleft()
			for coin in coins:
				if curr - coin >= 0 and curr - coin not in Visited:
					queue.append(curr - coin)
					Visited[curr - coin] = Visited[curr] + 1
				if 0 in Visited:
					return Visited[0]
		return -1


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		q = deque()
		q.append([amount, 0])
		level = 0
		seen = set()
		while q:
			(amt, level) = q.popleft()
			for n in coins:
				if amt - n == 0:
					return level + 1
				if amt - n in seen or amt - n < 0:
					continue
				seen.add(amt - n)
				q.append([amt - n, level + 1])
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		coins.sort()
		visited = {}
		sums = []
		for coin in coins:
			if coin == amount:
				return 1
			visited[coin] = 1
			sums.append(coin)
		q = []
		q.append((1, sums))
		while q:
			(count, sums) = q.pop()
			next_sums = []
			for coin in coins:
				for s in sums:
					current = coin + s
					if current < amount and current not in visited:
						visited[current] = 1
						next_sums.append(current)
					elif current == amount:
						return count + 1
					else:
						visited[current] = 1
			if next_sums:
				q.insert(0, (count + 1, next_sums))
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1 for i in range(amount + 1)]
		dp[0] = 0
		for i in range(amount + 1):
			for c in coins:
				if c <= i and dp[i] > dp[i - c] + 1:
					dp[i] = dp[i - c] + 1
		return -1 if dp[amount] > amount else dp[amount]


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		queue = deque([(amount, 0)])
		visited = set([amount])
		while queue:
			(remaining, steps) = queue.popleft()
			for coin in coins:
				if coin == remaining:
					return steps + 1
				elif coin < remaining:
					temp = remaining - coin
					if temp > 0 and temp not in visited:
						visited.add(temp)
						queue.append((temp, steps + 1))
		return -1


from collections import defaultdict

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		MAX = float('inf')
		dp = defaultdict(lambda : MAX)
		dp[0] = 0
		for i in range(1, amount + 1):
			dp[i] = 1 + min([dp[i - c] for c in coins])
		return -1 if dp[amount] == MAX else dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		l = [int(amount + 1)] * int(amount + 1)
		if amount == 0:
			return 0
		else:
			l[0] = 0
			coins.sort()
			for i in range(1, amount + 1):
				for coin in coins:
					remainder = i - coin
					if remainder < 0:
						break
					elif l[i] > l[remainder] + 1:
						l[i] = l[remainder] + 1
		if l[amount] == amount + 1:
			return -1
		else:
			return l[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort(reverse=True)
		queue = [amount]
		visit = {amount: 0}
		while queue:
			remain = queue.pop(0)
			for c in coins:
				branch = remain - c
				if 0 <= branch not in visit:
					queue.append(branch)
					visit.update({branch: visit[remain] + 1})
		return visit.get(0) or -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		visited = set([amount])
		candidates = [amount]
		res = 0
		while candidates:
			res += 1
			next_candidates = []
			for candidate in candidates:
				for coin in coins:
					if candidate - coin == 0:
						return res
					elif candidate - coin > 0 and candidate - coin not in visited:
						next_candidates.append(candidate - coin)
						visited.add(candidate - coin)
			candidates = next_candidates
		return -1


class Solution:

	def coinChange(self, denoms: List[int], n: int) -> int:
		if n == 0:
			return 0
		nodes = set([0])
		seen = set()
		count = 1
		while nodes:
			seen = seen | nodes
			next_nodes = set()
			for node in nodes:
				for denom in denoms:
					candidate = node + denom
					if candidate == n:
						return count
					elif candidate < n and candidate not in seen:
						next_nodes.add(candidate)
			count += 1
			nodes = next_nodes
		return -1
		pass


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		d = [0] + [float('inf')] * amount
		for v in range(1, len(d)):
			for c in coins:
				if c <= v and d[v] > d[v - c] + 1:
					d[v] = d[v - c] + 1
		return d[-1] if d[-1] < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		queue = deque()
		numCoins = 0
		seen = set()
		coins.sort(reverse=True)
		queue.append(amount)
		if amount == 0:
			return 0
		while queue:
			qlen = len(queue)
			numCoins += 1
			for i in range(qlen):
				x = queue.popleft()
				for coin in coins:
					if x - coin == 0:
						return numCoins
					elif x - coin > 0:
						if x - coin not in seen:
							queue.append(x - coin)
							seen.add(x - coin)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		result = -1

		def helper(coins: List[int], pos: int, left: int, current: int):
			if left % coins[pos] == 0:
				nonlocal result
				if result == -1 or result > current + left // coins[pos]:
					result = current + left // coins[pos]
				return
			if pos == len(coins) - 1:
				return
			for k in range(left // coins[pos], -1, -1):
				new_amount = left - coins[pos] * k
				new_count = current + k
				if result != -1 and result < new_count + (new_amount + coins[pos + 1] - 1) / coins[pos + 1]:
					break
				helper(coins, pos + 1, left - coins[pos] * k, current + k)
		helper(coins, 0, amount, 0)
		return result


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		queue = collections.deque([(0, 0)])
		seen = set()
		while queue:
			(curAmount, step) = queue.popleft()
			if curAmount == amount:
				return step
			for j in range(len(coins)):
				newAmount = curAmount + coins[j]
				if newAmount <= amount and newAmount not in seen:
					seen.add(newAmount)
					queue.append((newAmount, step + 1))
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		coins.sort()
		coins_set = set(coins)
		if amount in coins_set:
			return 1
		queue = deque([[amount, 0]])
		seen = set()
		processed = set()
		while queue:
			(rem, count) = queue.popleft()
			if rem in seen:
				continue
			seen.add(rem)
			for coin in coins:
				new_rem = rem - coin
				if new_rem == 0:
					return count + 1
				if new_rem > 0:
					if new_rem in coins_set:
						return count + 2
					if new_rem not in seen and new_rem not in processed:
						queue.append([new_rem, count + 1])
						processed.add(new_rem)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('+inf')] * (amount + 1)
		dp[0] = 0
		for cnt in range(1, amount + 1):
			for coin in coins:
				if cnt - coin >= 0 and dp[cnt - coin] + 1 < dp[cnt]:
					dp[cnt] = dp[cnt - coin] + 1
		if dp[amount] == float('+inf'):
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf') for _ in range(amount + 1)]
		dp[0] = 0
		for x in range(len(dp)):
			for coin in coins:
				if x < coin:
					continue
				if dp[x - coin] + 1 < dp[x]:
					dp[x] = dp[x - coin] + 1
		if dp[amount] == float('inf'):
			return -1
		else:
			return dp[x]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		rec = [0] * amount
		fr = [0]
		new = []
		l = 1
		while fr or new:
			if not fr:
				fr = new
				new = []
				l += 1
			cur = fr.pop(0)
			for c in coins:
				if cur + c == amount:
					return l
				if cur + c < amount and (not rec[cur + c]):
					new.append(cur + c)
					rec[cur + c] = 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = [float('inf') for _ in range(amount + 1)]
		memo[0] = 0
		for i in range(1, len(memo)):
			minv = float('inf')
			for coin in coins:
				if i - coin >= 0 and memo[i - coin] < minv:
					minv = memo[i - coin]
			memo[i] = 1 + minv
		return memo[amount] if memo[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cache = [0] * (amount + 1)
		for ind in range(1, amount + 1):
			min_coins = float('inf')
			for coin in coins:
				if ind - coin >= 0:
					coins_needed = cache[ind - coin] + 1
					if coins_needed < min_coins:
						min_coins = coins_needed
			cache[ind] = min_coins
		if cache[amount] == float('inf'):
			return -1
		return cache[amount]


class Solution:

	def coinChange(self, coins: [int], amount: int) -> int:
		summary = 0
		result = [float('inf')] * (amount + 1)
		result[0] = 0
		while summary <= amount:
			if result[summary] != -1:
				for i in coins:
					if summary + i <= amount and result[summary] + 1 < result[summary + i]:
						result[summary + i] = result[summary] + 1
			summary += 1
		return -1 if result[amount] == float('inf') else result[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		arr = [float('inf')] * (amount + 1)
		arr[0] = 0
		for i in range(amount + 1):
			for c in coins:
				if i + c > amount:
					continue
				if arr[i + c] > arr[i] + 1:
					arr[i + c] = arr[i] + 1
		if arr[-1] == float('inf'):
			return -1
		return arr[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		min_coins = [float('inf') for x in range(amount + 1)]
		min_coins[0] = 0
		for value in range(1, amount + 1):
			for coin in coins:
				if coin <= value:
					if min_coins[value - coin] + 1 < min_coins[value]:
						min_coins[value] = min_coins[value - coin] + 1
		if min_coins[amount] == float('inf'):
			return -1
		return min_coins[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		queue = [[amount, 0]]
		visited = {0}
		for q in queue:
			for c in coins:
				if q[0] == c:
					return q[1] + 1
				elif q[0] > c and q[0] - c not in visited:
					visited.add(q[0] - c)
					queue.append([q[0] - c, q[1] + 1])
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		m = [-1 for x in range(amount + 1)]
		m[0] = 0
		coins = sorted(coins)
		if amount < min(coins):
			return m[amount]
		m[coins[0]] = 1
		for x in range(coins[0], amount + 1):
			current_min = 10000000
			for y in coins:
				if y > x:
					continue
				if m[x - y] < current_min and m[x - y] != -1:
					current_min = m[x - y]
			if current_min == 10000000:
				m[x] = -1
			else:
				m[x] = current_min + 1
		print(m)
		return m[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] * (amount + 1)
		for i in range(1, len(dp)):
			dp[i] = float('inf')
			for j in coins:
				if i >= j and dp[i - j] + 1 < dp[i]:
					dp[i] = dp[i - j] + 1
		return -1 if dp[amount] == float('inf') else dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		table = [0] + [amount + 1 for _ in range(amount)]
		for i in range(1, amount + 1):
			for coin in coins:
				if coin <= i:
					sub_result = table[i - coin]
					if sub_result + 1 < table[i]:
						table[i] = sub_result + 1
		print(table)
		if table[amount] > amount:
			return -1
		else:
			return table[amount]


class Solution:

	def bfs(self, cur, coins):
		if cur == 0:
			return 0
		queue = [(0, cur)]
		visited = {}
		while queue:
			(times, cur) = heapq.heappop(queue)
			for c in coins:
				if c == cur:
					return times + 1
				if c < cur:
					if cur - c not in visited:
						heapq.heappush(queue, (times + 1, cur - c))
						visited[cur - c] = True
		return -1

	def coinChange(self, coins: List[int], amount: int) -> int:
		return self.bfs(amount, coins)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			tmp = float('inf')
			for c in coins:
				if i - c >= 0:
					if tmp > dp[i - c] + 1:
						tmp = dp[i - c] + 1
			dp[i] = tmp
		return dp[amount] if dp[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp_mat = [-1] * (amount + 1)
		dp_mat[0] = 0
		for i in range(1, amount + 1):
			min_num = None
			for denom in coins:
				if denom <= i and dp_mat[i - denom] != -1:
					temp = 1 + dp_mat[i - denom]
					if not min_num:
						min_num = temp
					elif temp < min_num:
						min_num = temp
			if min_num:
				dp_mat[i] = min_num
		return dp_mat[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = [float('inf')] * (amount + 1)
		calculated = [False] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			if coin <= amount:
				dp[coin] = 1
				calculated[coin] = True
		for i in range(1, amount + 1):
			if not calculated[i]:
				candidates = [dp[i - coin] for coin in coins if i >= coin]
				if candidates:
					dp[i] = min(candidates) + 1
					calculated[i] = True
		if dp[-1] == float('inf'):
			return -1
		else:
			return dp[-1]


class Solution:

	def do_du_tab(self, coins, amount):
		dp_tab = [math.inf for _ in range(amount + 1)]
		dp_tab[0] = 0
		for a in range(1, amount + 1):
			potential = []
			for coin in coins:
				potential.append(dp_tab[a - coin] + 1)
			dp_tab[a] = min(potential)
		return dp_tab[-1] if dp_tab[-1] != float('inf') else -1

	def do_something(self, coins, amount):
		dp_tab = [math.inf for _ in range(amount + 1)]
		dp_tab[0] = 0
		for i in range(1, amount + 1):
			temp = []
			for coin in coins:
				temp.append(dp_tab[i - coin])
			dp_tab[i] = min(temp) + 1
		return dp_tab[amount] if dp_tab[amount] != float('inf') else -1

	def coinChange(self, coins: List[int], amount: int) -> int:
		if len(coins) == 0:
			return 0
		if amount == 0:
			return 0
		c = [coin for coin in coins if coin <= amount]
		if len(c) == 0:
			return -1
		return self.do_something(c, amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			curr_min = amount + 1
			for coin in coins:
				cand = amount + 1
				if i - coin >= 0:
					cand = dp[i - coin] + 1
				if cand < curr_min:
					curr_min = cand
			dp[i] = curr_min
		return -1 if dp[len(dp) - 1] == amount + 1 else dp[len(dp) - 1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		return self.coinChangeBFS(coins, amount)

	def coinChangeBFS(self, coins: List[int], amount: int) -> int:
		if amount == 0 or not coins:
			return 0
		queue = deque([amount])
		visited = set([amount])
		depth = 0
		while queue:
			length = len(queue)
			depth += 1
			for i in range(length):
				remaining = queue.popleft()
				for c in coins:
					if remaining - c == 0:
						return depth
					elif remaining - c < 0:
						continue
					elif remaining - c not in visited:
						queue.append(remaining - c)
						visited.add(remaining - c)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		values = [-1 for i in range(amount + 1)]
		values[0] = 0
		for i in coins:
			for j in range(1, len(values)):
				if j >= i:
					if values[j - i] == -1:
						continue
					curr_num_coins = 1 + values[j - i]
					if values[j] == -1 or values[j] > curr_num_coins:
						values[j] = curr_num_coins
		return values[amount]


class Solution:

	def coinChange(self, nums: List[int], amount: int) -> int:
		MAX = float('inf')
		dp = [0] + [MAX] * amount
		for i in range(1, amount + 1):
			dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in nums]) + 1
		return [dp[amount], -1][dp[amount] == MAX]


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = [float('inf')] * (amount + 1)
		dp[amount] = 0
		queue = deque()
		queue.append(amount)
		while len(queue) != 0:
			val = queue.popleft()
			for coin in coins:
				if val - coin == 0:
					return dp[val] + 1
				if val - coin > 0:
					if dp[val] + 1 < dp[val - coin]:
						dp[val - coin] = dp[val] + 1
						queue.append(val - coin)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		MAX = amount + 1
		coins.sort(reverse=True)
		dp = [MAX] * MAX
		dp[0] = 0
		for i in range(1, MAX):
			dp[i] = min([dp[i - c] if i >= c else MAX for c in coins])
			dp[i] = dp[i] + 1 if dp[i] != MAX else dp[i]
		return -1 if dp[-1] == MAX else dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [-1] * amount
		for x in range(amount + 1):
			if dp[x] < 0:
				continue
			for c in coins:
				if x + c > amount:
					continue
				if dp[x + c] < 0 or dp[x + c] > dp[x] + 1:
					dp[x + c] = dp[x] + 1
		return dp[amount]


class Solution:

	def coinChangeCopy(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		dp = [amount + 1] * (amount + 1)
		for i in range(amount + 1):
			if i in coins:
				dp[i] = 1
				continue
			candidates = [dp[i - coin] + 1 for coin in coins if i - coin > 0]
			if candidates:
				dp[i] = min(candidates)
		print(dp)
		return -1 if dp[amount] > amount else dp[amount]

	def coinChange(self, coins, amount):
		if not amount:
			return 0
		coin_nums = [amount + 1] * (amount + 1)
		coins_set = set(coins)
		for i in range(amount + 1):
			if i in coins_set:
				coin_nums[i] = 1
				continue
			candidates = [coin_nums[i - coin] + 1 for coin in coins if i - coin > 0]
			if candidates:
				coin_nums[i] = min(candidates)
		return coin_nums[amount] if coin_nums[amount] <= amount else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort()
		cnt = 0
		toCheck = {amount}
		while toCheck:
			cnt += 1
			tmp = set()
			for x in toCheck:
				for y in coins:
					if y == x:
						return cnt
					if y > x:
						break
					tmp.add(x - y)
			if not tmp:
				return -1
			toCheck = tmp

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [float('inf')] * amount
		for i in range(1, amount + 1):
			dp[i] = min((dp[i - c] if i - c >= 0 else float('inf') for c in coins)) + 1
		return dp[-1] if dp[-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [-1] * amount
		for coin in coins:
			for idx in range(coin, len(dp)):
				if dp[idx - coin] != -1:
					if dp[idx] != -1:
						dp[idx] = min(dp[idx - coin] + 1, dp[idx])
					else:
						dp[idx] = dp[idx - coin] + 1
		return dp[amount]


class Solution(object):

	def coinChange(self, coins, amount):
		MAX = float('inf')
		dp = [0] + [MAX] * amount
		for i in range(1, amount + 1):
			dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1
		if dp[amount] == MAX:
			return -1
		return dp[amount]
		return [dp[amount], -1][dp[amount] == MAX]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		for i in range(min(coins), amount + 1):
			tmp = list()
			for coin in coins:
				if i - coin < 0:
					tmp.append(float('inf'))
				else:
					tmp.append(dp[i - coin])
			dp[i] = min(tmp) + 1
		return dp[-1] if dp[-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		coins = [coin for coin in coins if coin <= amount]
		if not coins:
			return -1
		dp = [0 for i in range(amount + max(coins) + 10)]
		for coin in coins:
			dp[coin] = 1
		for i in range(1, amount + 1):
			for coin in coins:
				if dp[i] >= 1:
					if dp[i + coin] == 0:
						dp[i + coin] = dp[i] + 1
					elif dp[i] + 1 < dp[i + coin]:
						dp[i + coin] = dp[i] + 1
		if not dp[amount]:
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def dfs(start, amt, n_coins):
			nonlocal min_coins
			coin = coins[start]
			div = amt // coin
			n_coins += div
			amt %= coin
			if amt == 0:
				min_coins = min(min_coins, n_coins)
				return
			if start < len_coins:
				dfs(start + 1, amt, n_coins)
				next_coin = coins[start + 1]
				for _ in range(div):
					amt += coin
					n_coins -= 1
					if (min_coins - n_coins - 1) * next_coin + 1 > amt:
						dfs(start + 1, amt, n_coins)
					else:
						break
		len_coins = len(coins) - 1
		coins.sort(reverse=True)
		min_coins = float('inf')
		dfs(0, amount, 0)
		return min_coins if min_coins < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		a = [amount + 1] * (amount + 1)
		a[0] = 0
		for i in range(1, amount + 1):
			mlist = [a[i - c] for c in coins if i - c >= 0]
			if len(mlist) > 0:
				a[i] = 1 + min(mlist)
		print(a)
		if a[amount] > amount:
			return -1
		else:
			return a[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		coins_set = set(coins)
		for i in range(amount + 1):
			if i in coins_set:
				dp[i] = 1
				continue
			candidates = [dp[i - c] + 1 for c in coins if i - c >= 0]
			if candidates:
				dp[i] = min(candidates)
		return dp[amount] if dp[amount] <= amount else -1


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		path_length = []
		path_length.append(0)
		for value in range(1, amount + 1):
			min_path_value = math.inf
			for coin in coins:
				path_index = value - coin
				if path_index > -1 and path_length[path_index] != -1:
					current_min_path = path_length[path_index] + 1
					if current_min_path < min_path_value:
						min_path_value = current_min_path
			path_length.append(min_path_value)
		return path_length[amount] if path_length[amount] < math.inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		cache = [0] * (amount + 1)
		for i in range(1, amount + 1):
			min_count = float('inf')
			for coin in coins:
				if i - coin >= 0:
					current_min_coin = cache[i - coin] + 1
					if min_count > current_min_coin:
						min_count = current_min_coin
			cache[i] = min_count
		if cache[amount] in [0, float('inf')]:
			return -1
		return cache[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [None for i in range(amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			result = None
			for coin in coins:
				if i - coin >= 0:
					tmp = dp[i - coin]
					if tmp is not None and (result is None or tmp + 1 < result):
						result = tmp + 1
			dp[i] = result
		if dp[-1] is None:
			return -1
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		arr = [float('inf')] * (amount + 1)
		arr[0] = 0
		for i in range(1, len(arr)):
			min_choices = []
			for x in coins:
				if i - x >= 0:
					min_choices.append(1 + arr[i - x])
			if min_choices:
				arr[i] = min(min_choices)
		if arr[amount] == float('inf'):
			return -1
		else:
			return arr[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins and amount:
			return -1
		if not amount:
			return 0
		target = [0] * (amount + 1)
		target[0] = 1
		for i in range(len(coins) - 1, -1, -1):
			coin = coins[i]
			j = 0
			while j <= amount:
				if target[j] == 0:
					j += 1
					continue
				next_idx = j + coin
				if next_idx > amount:
					break
				if target[j] > 0 and target[next_idx] > target[j] or target[next_idx] == 0:
					target[next_idx] = target[j] + 1
				j += 1
		print(target)
		if target[amount]:
			return target[amount] - 1
		else:
			return -1


class Solution:

	def __init__(self):
		self.min_coins = float('inf')

	def coinChange(self, coins: List[int], amount: int) -> int:

		def getChange(num_coins, need, start):
			divided_coin = need // coins[start]
			if num_coins + divided_coin >= self.min_coins:
				return
			if need % coins[start] == 0:
				self.min_coins = min(self.min_coins, divided_coin + num_coins)
				return
			if start == len(coins) - 1:
				return
			for num_used in range(divided_coin, -1, -1):
				new_need = need - coins[start] * num_used
				getChange(num_coins + num_used, new_need, start + 1)
		coins = sorted(coins, reverse=True)
		getChange(0, amount, 0)
		return self.min_coins if self.min_coins < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		T = [float('inf')] * (amount + 1)
		T[0] = 0
		for amnt in range(1, amount + 1):
			curr_min = float('inf')
			for k in range(len(coins)):
				if coins[k] <= amnt:
					val = 1 + T[amnt - coins[k]]
					if val < curr_min:
						curr_min = val
			T[amnt] = curr_min
		return -1 if T[-1] == float('inf') else T[-1]


from typing import List

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		solution = -1
		dp = [0] * (amount + 1)
		for i in range(1, amount + 1):
			dp[i] = min([dp[i - coin] for coin in coins if i - coin >= 0] + [10000]) + 1
		if dp[-1] != 10001:
			solution = dp[-1]
		return solution


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins, reverse=True)
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			if i - coins[-1] < 0:
				continue
			for coin in coins:
				index = i - coin
				if index >= 0 and dp[index] != -1:
					value = dp[index] + 1
					if dp[i] == -1 or dp[i] > value:
						dp[i] = value
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			for x in range(coin, amount + 1):
				dp[x] = min(dp[x], dp[x - coin] + 1)
		return dp[amount] if dp[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		self.ret = float('inf')

		def recurrent(index, coins, amount, current):
			first = coins[index]
			n = amount // first
			remainder = amount % first
			if remainder == 0:
				self.ret = min(self.ret, current + n)
			else:
				l = len(coins)
				while remainder <= amount and index < l - 1 and (current + n < self.ret):
					recurrent(index + 1, coins, remainder, current + n)
					n -= 1
					remainder += first
			return
		recurrent(0, coins, amount, 0)
		if self.ret == float('inf'):
			return -1
		else:
			return self.ret


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount <= 0:
			return 0
		f = [float('inf')] * (amount + 1)
		f[0] = 0
		for c in coins:
			for a in range(c, amount + 1):
				f[a] = min(f[a], f[a - c] + 1)
		return f[amount] if f[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		numWays = [float('inf')] * (amount + 1)
		numWays[0] = 0
		for coin in coins:
			for value in range(coin, amount + 1):
				numWays[value] = min(numWays[value], 1 + numWays[value - coin])
		print(numWays[amount])
		return numWays[amount] if numWays[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1 for _ in range(amount + 1)]
		dp[0] = 0
		for coin in coins:
			for a in range(coin, amount + 1):
				dp[a] = min(dp[a], dp[a - coin] + 1)
		res = dp[amount] if dp[amount] < amount + 1 else -1
		return res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		mem = [-1] * (amount + 1)
		mem[0] = 0
		for i in range(1, amount + 1):
			m = math.inf
			for c in coins:
				if i - c >= 0:
					if mem[i - c] != -1 and mem[i - c] + 1 < m:
						m = mem[i - c] + 1
			if m != math.inf:
				mem[i] = m
		print(mem)
		return mem[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [float('inf')] * amount
		for c in coins:
			for j in range(c, amount + 1):
				dp[j] = min(dp[j], dp[j - c] + 1)
		return dp[-1] if dp[-1] < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [math.inf] * (amount + 1)
		dp[0] = 0
		for coin in coins:
			for idx in range(coin, amount + 1):
				prev_coins_ct = dp[idx - coin]
				dp[idx] = min(prev_coins_ct + 1, dp[idx])
		if dp[-1] == math.inf:
			return -1
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for idx in range(amount + 1):
			tmp = []
			for coin in coins:
				if idx - coin >= 0 and dp[idx - coin] != -1:
					tmp.append(dp[idx - coin])
			if tmp:
				dp[idx] = min(tmp) + 1
		print(dp)
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 0:
			return -1
		coins = sorted(coins)
		d = [amount + 1] * (amount + 1)
		d[0] = 0
		for i in range(amount + 1):
			for j in coins:
				if j <= i:
					d[i] = min(d[i], d[i - j] + 1)
				else:
					break
		if d[-1] > amount:
			return -1
		else:
			return d[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for i in range(len(coins)):
			if coins[i] <= amount:
				dp[coins[i]] = 1
		for i in range(1, amount + 1):
			if dp[i] == -1:
				comparison = []
				for c in coins:
					if i - c >= 0 and dp[i - c] != -1:
						comparison.append(dp[i - c])
				if comparison:
					dp[i] = min(comparison) + 1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = [float('inf') for _ in range(amount + 1)]
		memo[0] = 0
		for c in coins:
			for i in range(c, len(memo)):
				memo[i] = min(1 + memo[i - c], memo[i])
		return memo[amount] if memo[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			for j in coins:
				if i >= j:
					dp[i] = min(dp[i], dp[i - j] + 1)
		if dp[amount] == amount + 1:
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		rs = [amount + 1] * (amount + 1)
		rs[0] = 0
		for i in range(1, amount + 1):
			for c in coins:
				if i >= c:
					rs[i] = min(rs[i], rs[i - c] + 1)
		if rs[amount] == amount + 1:
			return -1
		return rs[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [sys.maxsize] * (amount + 1)
		dp[0] = 0
		for i in range(1, len(dp)):
			for c in coins:
				if c <= i:
					dp[i] = min(dp[i], dp[i - c] + 1)
		if dp[amount] == sys.maxsize:
			return -1
		return dp[amount]


import math

def rec(coins, amount, used_coins, res):
	if amount == 0:
		res[0] = min(res[0], used_coins)
	elif coins and (res[0] - used_coins) * coins[-1] >= amount:
		for i in range(amount // coins[-1], -1, -1):
			rec(coins[:-1], amount - i * coins[-1], used_coins + i, res)

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		res = [math.inf]
		rec(sorted(coins), amount, 0, res)
		return res[0] if res[0] != math.inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or len(coins) == 0:
			return 0
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for i in range(amount + 1):
			for j in coins:
				if j <= i:
					dp[i] = min(dp[i], dp[i - j] + 1)
		if dp[-1] > amount:
			return -1
		else:
			return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		if amount == 0:
			return 0
		changes = [amount + 1] * (amount + 1)
		changes[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				if coin > i:
					break
				else:
					changes[i] = min(changes[i], changes[i - coin] + 1)
		if changes[-1] != amount + 1:
			return changes[-1]
		else:
			return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return amount
		dp = [1000000000.0 for _ in range(amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			k = 1000000000.0
			for c in coins:
				if i - c >= 0:
					k = min(k, dp[i - c] + 1)
			if k != 1000000000.0:
				dp[i] = k
		return -1 if dp[amount] == 1000000000.0 else dp[amount]


class Solution:

	def coinChange(self, coins, amount):
		coins.sort(reverse=True)
		(lenc, self.res) = (len(coins), 2 ** 31 - 1)

		def dfs(pt, rem, count):
			if not rem:
				self.res = min(self.res, count)
			for i in range(pt, lenc):
				if coins[i] <= rem < coins[i] * (self.res - count):
					dfs(i, rem - coins[i], count + 1)
		for i in range(lenc):
			dfs(i, amount, 0)
		return self.res if self.res < 2 ** 31 - 1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		dp = [amount + 1 for _ in range(amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				if coin > i:
					break
				dp[i] = min(dp[i], dp[i - coin] + 1)
		res = dp[amount] if dp[amount] < amount + 1 else -1
		return res


import math

class Solution:

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


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(maxsize=None)
		def giveChange(target):
			if target == 0:
				return 0
			if target < 0:
				return -1
			minForTarget = None
			for coin in coins:
				result = giveChange(target - coin)
				if result != -1:
					minForTarget = result + 1 if not minForTarget else min(result + 1, minForTarget)
			return minForTarget or -1
		return giveChange(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		n = len(coins)
		dp = [0] + [amount + 1 for i in range(amount)]
		for i in range(1, amount + 1):
			for c in coins:
				if i >= c:
					dp[i] = min(dp[i - c] + 1, dp[i])
		return dp[amount] if dp[amount] < amount + 1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [float('inf')] * amount
		print(dp)
		for coin in coins:
			for i in range(len(dp)):
				if coin <= i:
					dp[i] = min(dp[i], dp[i - coin] + 1)
		return dp[-1] if dp[-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		self.min = 2 ** 31 - 1

		def dfs(index, amount, count):
			if amount == 0:
				self.min = min(self.min, count)
			if amount < 0:
				return
			for i in range(index, len(coins)):
				if coins[i] * (self.min - count) > amount >= coins[i]:
					dfs(i, amount - coins[i], count + 1)
		dfs(0, amount, 0)
		return self.min if self.min != 2 ** 31 - 1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		ary = [amount + 1] * (amount + 1)
		ary[0] = 0
		for i in range(1, len(ary)):
			for coin in coins:
				if i - coin < 0:
					continue
				ary[i] = min(ary[i], ary[i - coin] + 1)
		return ary[amount] if ary[amount] < amount + 1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		numOfCoins = [float('inf') for x in range(amount + 1)]
		numOfCoins[0] = 0
		for coin in coins:
			for num in range(len(numOfCoins)):
				if coin <= num:
					numOfCoins[num] = min(numOfCoins[num], numOfCoins[num - coin] + 1)
		return numOfCoins[amount] if numOfCoins[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		MAX = float('inf')
		dp = [0] + [MAX] * amount
		for i in range(1, amount + 1):
			for coin in coins:
				if i - coin >= 0:
					dp[i] = min(dp[i], dp[i - coin] + 1)
		if dp[-1] == MAX:
			return -1
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		MAX = amount + 10
		dp = [MAX for i in range(amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			curr = i
			for coin in coins:
				prev = curr - coin
				if prev >= 0:
					dp[curr] = min(dp[curr], dp[prev] + 1)
		return dp[amount] if dp[amount] != MAX else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [-1 for i in range(amount + 1)]
		dp[0] = 0
		for coin in coins:
			for i in range(coin, amount + 1):
				if i == coin:
					dp[i] = 1
				elif dp[i] == -1 and dp[i - coin] != -1:
					dp[i] = dp[i - coin] + 1
				elif dp[i] != -1 and dp[i - coin] != -1:
					dp[i] = min(dp[i], dp[i - coin] + 1)
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def change_memo(coins, amount, memo):
			if amount not in memo:
				if amount == 0:
					best = 0
				elif amount < 0:
					best = -1
				else:
					best = None
					for c in coins:
						res = change_memo(coins, amount - c, memo)
						if res == -1:
							continue
						if best is None or res < best:
							best = res
					if best is None:
						best = -1
					else:
						best += 1
				memo[amount] = best
			return memo[amount]
		memo = {}
		change_memo(coins, amount, memo)
		return memo[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		min_coins = float('inf')

		def count_coins(start_coin, coin_count, remaining_amount):
			nonlocal min_coins
			if remaining_amount == 0:
				min_coins = min(min_coins, coin_count)
				return
			for i in range(start_coin, len(coins)):
				remaining_coin_allowance = min_coins - coin_count
				max_amount_possible = coins[i] * remaining_coin_allowance
				if coins[i] <= remaining_amount and remaining_amount < max_amount_possible:
					count_coins(i, coin_count + 1, remaining_amount - coins[i])
		count_coins(0, 0, amount)
		return min_coins if min_coins < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		curr = [float('inf')] * (amount + 1)
		curr[0] = 0
		coins = sorted(coins)
		for num in range(amount + 1):
			for c in coins:
				if num - c < 0:
					break
				curr[num] = min(curr[num], curr[num - c] + 1)
		return curr[amount] if curr[amount] < float('inf') else -1


import sys

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [sys.maxsize] * (amount + 1)
		if amount == 0:
			return 0
		dp[amount] = 0
		for i in range(amount, -1, -1):
			for coin in coins:
				if i - coin >= 0:
					dp[i - coin] = min(dp[i] + 1, dp[i - coin])
		return -1 if dp[0] == sys.maxsize else dp[0]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(maxsize=None)
		def _recursive(a):
			if a == 0:
				return 0
			min_n = 1000000000.0
			for c in coins:
				if c <= a:
					sub_a = _recursive(a - c)
					if sub_a != -1:
						min_n = min(min_n, sub_a + 1)
			return min_n if min_n != 1000000000.0 else -1
		return _recursive(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		res = {}
		res[0] = 0
		for x in range(amount + 1)[1:]:
			prevs = [x - c for c in coins]
			this_res = min([res.get(y, 2 ** 31) for y in prevs]) + 1
			res[x] = this_res
		if res[amount] >= 2 ** 31:
			return -1
		else:
			return res[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort()
		coins.reverse()
		print(coins)
		change = [-1] * (amount + 1)
		change[0] = 0
		for i in range(1, amount + 1):
			for c1 in coins:
				if c1 > i:
					continue
				c2 = change[i - c1]
				if c2 >= 0:
					if change[i] == -1:
						change[i] = c2 + 1
					else:
						change[i] = min(c2 + 1, change[i])
		return change[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if len(coins) == 1:
			if amount % coins[0] == 0:
				return amount // coins[0]
			return -1
		dp = [0] * (amount + 1)
		for i in range(1, amount + 1):
			if i in set(coins):
				dp[i] = 1
				continue
			min_coins = float('inf')
			for coin in coins:
				if i - coin >= 0:
					min_coins = min(dp[i - coin], min_coins)
			dp[i] = min_coins + 1
		if dp[amount] == float('inf'):
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		amount_list = [i for i in range(amount + 1)]
		for i in range(amount + 1):
			if i == 0:
				amount_list[i] = 0
			elif i in coins:
				amount_list[i] = 1
			else:
				temp = []
				for coin in coins:
					if amount_list[i] - coin >= 0:
						remainder = amount_list[i] - coin
						min_coin = amount_list[remainder]
						if min_coin != -1:
							temp.append(min_coin)
				if len(temp) == 0:
					amount_list[i] = -1
				else:
					amount_list[i] = min(temp) + 1
		return amount_list[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def _fewest(cs, amt):
			nonlocal memo
			if amt not in memo:
				if amt < 0:
					memo[amt] = -1
				elif amt == 0:
					memo[amt] = 0
				else:
					fewest = -1
					for c in cs:
						f = _fewest(cs, amt - c)
						if f != -1 and (fewest == -1 or f + 1 < fewest):
							fewest = f + 1
					memo[amt] = fewest
			return memo[amt]
		return _fewest(coins, amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		mem = {}
		mem[0] = 0

		def rec(amount):
			if amount < 0:
				return -1
			if amount in mem:
				return mem[amount]
			m = math.inf
			for c in coins:
				n = rec(amount - c)
				if n != -1 and n + 1 < m:
					m = n + 1
			if m == math.inf:
				m = -1
			mem[amount] = m
			return m
		if amount == 0:
			return 0
		return rec(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for i in range(len(coins)):
			coin = coins[i]
			for j in range(1, amount + 1):
				sameCoin = amount + 1
				if j - coin >= 0:
					dp[j] = min(dp[j - coin] + 1, dp[j])
		return dp[amount] if dp[amount] != amount + 1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for partial_amount in range(1, amount + 1):
			for j in range(len(coins)):
				if coins[j] <= partial_amount:
					dp[partial_amount] = min(dp[partial_amount], dp[partial_amount - coins[j]] + 1)
		return dp[amount] if dp[amount] <= amount else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] + [float('inf')] * amount
		coinValues = collections.defaultdict(list)
		for coin in coins:
			for i in range(coin, amount + 1):
				if dp[i - coin] + 1 < dp[i]:
					dp[i] = dp[i - coin] + 1
					coinValues[i] = coinValues[i - coin] + [coin]
		print(coinValues[amount])
		return dp[-1] if dp[-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		num_ways = (amount + 1) * [-1]
		num_ways[0] = 0
		for v in range(1, amount + 1):
			fewest = float('inf')
			for c in coins:
				if v - c >= 0 and num_ways[v - c] != -1:
					fewest = min(num_ways[v - c], fewest)
			if fewest != float('inf'):
				num_ways[v] = 1 + fewest
		return num_ways[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helpCoins(coins, amount, cache):
			if amount < 0:
				return -1
			if amount == 0:
				return 0
			if amount in cache:
				return cache[amount]
			curr_min = 999
			for coin in coins:
				to_go = helpCoins(coins, amount - coin, cache)
				if to_go >= 0 and to_go < curr_min:
					curr_min = to_go + 1
			if curr_min == 999:
				cache[amount] = -1
			else:
				cache[amount] = curr_min
			return cache[amount]
		return helpCoins(coins, amount, {})


import collections

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		seen = set()
		queue = collections.deque()
		for coin in coins:
			queue.append((amount - coin, 1))
		while queue:
			curr = queue.popleft()
			if curr[0] == 0:
				return curr[1]
			if curr[0] < 0 or curr[0] in seen:
				continue
			seen.add(curr[0])
			for coin in coins:
				queue.append((curr[0] - coin, curr[1] + 1))
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		memo = {}

		def helper(target, options):
			if target in memo:
				return memo[target]
			else:
				best = None
				for opt in options:
					if opt == target:
						memo[target] = 1
						return 1
					elif opt < target:
						cont = helper(target - opt, options)
						if cont is not None and (best is None or cont + 1 < best):
							best = cont + 1
				memo[target] = best
				return best
		output = helper(amount, coins)
		return output if output is not None else -1


class Solution:

	def util(self, memo, coins, amount):
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		minarr = []
		for coin in coins:
			if amount - coin not in memo:
				memo[amount - coin] = self.util(memo, coins, amount - coin)
			minarr.append(memo[amount - coin])
		minarr = [m for m in minarr if m != -1]
		if not minarr:
			return -1
		return min(minarr) + 1

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}
		return self.util(memo, coins, amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		D = [0] * (amount + 1)

		def helper(rem):
			nonlocal D
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if D[rem] != 0:
				return D[rem]
			minn = float('inf')
			for coin in coins:
				res = helper(rem - coin)
				if res >= 0 and res < minn:
					minn = res + 1
			if minn == float('inf'):
				D[rem] = -1
			else:
				D[rem] = minn
			return D[rem]
		return helper(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [None for i in range(0, amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			min_cost = float('inf')
			for j in range(0, len(coins)):
				if coins[j] <= i:
					min_cost = min(min_cost, dp[i - coins[j]] + 1)
			dp[i] = min_cost
		if dp[-1] > amount:
			return -1
		return dp[-1]
		coinsNeeded = {}
		coinsNeeded[0] = 0
		for n in coins:
			coinsNeeded[n] = 1

		def findMinCoins(amount):
			if amount < 0:
				return float('inf')
			if amount in coinsNeeded:
				return coinsNeeded[amount]
			for n in coins:
				coinsUsed = 1 + findMinCoins(amount - n)
				if amount in coinsNeeded:
					coinsNeeded[amount] = min(coinsUsed, coinsNeeded[amount])
				else:
					coinsNeeded[amount] = coinsUsed
			return coinsNeeded[amount]
		findMinCoins(amount)
		if coinsNeeded[amount] == float('inf'):
			return -1
		return coinsNeeded[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		coins.sort()
		for i in range(amount + 1):
			for j in range(len(coins)):
				if coins[j] <= amount:
					dp[i] = min(dp[i], 1 + dp[i - coins[j]])
				else:
					break
		if dp[amount] > amount:
			return -1
		else:
			return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.coins = coins
		self.amount = amount
		self.cache = {}
		res = self.getValue(self.amount)
		if res is None:
			return -1
		else:
			return res

	def getValue(self, amount):
		if amount in self.cache:
			return self.cache[amount]
		if amount < 0:
			return None
		if amount == 0:
			return 0
		if amount in self.coins:
			return 1
		min_count = None
		for coin in self.coins:
			count = self.getValue(amount - coin)
			if count is not None:
				if min_count is None or min_count > count + 1:
					min_count = count + 1
		self.cache[amount] = min_count
		return min_count


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		s = list()
		import sys
		for i in range(0, amount + 1):
			s.append(sys.maxsize)
		s[0] = 0
		for i in range(1, amount + 1):
			m = sys.maxsize
			for j in range(0, len(coins)):
				if i - coins[j] >= 0:
					m = min(m, s[i - coins[j]])
			if m == sys.maxsize:
				s[i] = m
			else:
				s[i] = m + 1
		if s[amount] == sys.maxsize:
			s[amount] = -1
		return s[amount]


class Solution:

	def coinChange(self, coins, amount):
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			for j in range(0, len(coins)):
				if coins[j] <= i:
					dp[i] = min(dp[i], dp[i - coins[j]] + 1)
		return -1 if dp[amount] > amount else dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 0 or not coins:
			return -1
		if amount == 0:
			return 0
		min_com = [0 for i in range(amount + 1)]
		for i in range(1, amount + 1):
			for c in coins:
				if i >= c and (min_com[i - c] > 0 or i - c == 0):
					if min_com[i] == 0:
						min_com[i] = min_com[i - c] + 1
					else:
						min_com[i] = min(min_com[i], min_com[i - c] + 1)
		if min_com[amount] == 0:
			return -1
		return min_com[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.smallest = float('inf')
		coins.sort(reverse=True)
		self.dfs(coins, amount, 0)
		return -1 if type(self.smallest) is float else self.smallest

	def dfs(self, coins, amount, prev_count):
		if len(coins) == 0:
			return
		if amount % coins[0] == 0:
			self.smallest = min(self.smallest, prev_count + amount // coins[0])
		else:
			for k in range(amount // coins[0], -1, -1):
				if prev_count + k >= self.smallest:
					break
				self.dfs(coins[1:], amount - k * coins[0], prev_count + k)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def make_change(sum_remaining, coins, mem):
			if sum_remaining < 0:
				return -1
			elif sum_remaining == 0:
				return 0
			elif mem[sum_remaining]:
				return mem[sum_remaining]
			else:
				min_coins = amount + 1
				for coin in coins:
					if sum_remaining - coin >= 0:
						prev_coins = make_change(sum_remaining - coin, coins, mem)
						curr_coins = 1 + prev_coins
						if curr_coins > 0 and curr_coins < min_coins:
							min_coins = curr_coins
				mem[sum_remaining] = min_coins
				return mem[sum_remaining]
		mem = [None] * (amount + 1)
		ans = make_change(amount, coins, mem)
		if ans == amount + 1:
			return -1
		else:
			return ans


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		counts = [0] * amount
		return f(coins, amount, counts)

def f(coins, amount, counts):
	if amount < 0:
		return -1
	if amount == 0:
		return 0
	if counts[amount - 1] != 0:
		return counts[amount - 1]
	min_val = math.inf
	for c in coins:
		res = f(coins, amount - c, counts)
		if res >= 0 and res < min_val:
			min_val = 1 + res
	if min_val == math.inf:
		counts[amount - 1] = -1
	else:
		counts[amount - 1] = min_val
	return counts[amount - 1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(maxsize=None)
		def helper(amount):
			if amount <= 0:
				return 0
			min_so_far = math.inf
			for i in range(len(coins)):
				if coins[i] <= amount:
					min_so_far = min(min_so_far, 1 + helper(amount - coins[i]))
			return min_so_far
		result = helper(amount)
		if result == math.inf:
			return -1
		return result


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		T = len(coins)
		dp = [0 for i in range(amount + 1)]
		for n in range(1, amount + 1):
			dp[n] = math.inf
			for i in range(T):
				if n - coins[i] >= 0:
					subProbSol = dp[n - coins[i]]
					dp[n] = min(dp[n], subProbSol + 1)
		if dp[amount] == math.inf:
			return -1
		else:
			return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		numCoins = [float('inf') for i in range(amount)]
		for coin in coins:
			if coin - 1 < amount:
				numCoins[coin - 1] = 1
		for i in range(amount):
			minCoin = float('inf')
			change = True
			for coin in coins:
				if i == coin - 1:
					change = False
					break
				if i - coin >= 0:
					minCoin = min(numCoins[i - coin], minCoin)
			if change and minCoin != float('inf'):
				numCoins[i] = minCoin + 1
		if numCoins[-1] == float('inf'):
			return -1
		return numCoins[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helper(remAmt, coins):
			nonlocal mem
			if remAmt in mem:
				return mem[remAmt]
			minCoins = float('inf')
			for coin in coins:
				if coin <= remAmt:
					result = 1 + helper(remAmt - coin, coins)
					minCoins = min(minCoins, result)
				else:
					break
			mem[remAmt] = minCoins
			return minCoins
		if amount < 1:
			return 0
		mem = {0: 0}
		coins.sort()
		minCoins = helper(amount, coins)
		if minCoins == float('inf'):
			return -1
		return minCoins


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}
		return self.aux(coins, amount, memo)

	def aux(self, coins, amount, memo):
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if amount in memo.keys():
			return memo[amount]
		minimum = 999999999
		for x in coins:
			temp = self.aux(coins, amount - x, memo)
			if temp < minimum and temp >= 0:
				minimum = temp
		if minimum == 999999999:
			memo[amount] = -1
			return memo[amount]
		memo[amount] = 1 + minimum
		return memo[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = set(coins)
		d = {}
		if amount == 0:
			return 0

		def solve(amt):
			if amt in d:
				return d[amt]
			if amt <= 0:
				return -1
			if amt in coins:
				d[amt] = 1
				return d[amt]
			poss = []
			for c in coins:
				search = amt - c
				if search < 1:
					continue
				val = solve(search)
				if val != -1:
					poss.append(val)
			if len(poss) != 0:
				d[amt] = 1 + min(poss)
			else:
				d[amt] = -1
			return d[amt]
		return solve(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		self.cache = [0] * (amount + 1)
		return self.coin_change(coins, amount)

	def coin_change(self, coins, remainder):
		if remainder < 0:
			return -1
		if remainder == 0:
			return 0
		if self.cache[remainder] != 0:
			return self.cache[remainder]
		system_max = sys.maxsize
		minimum = system_max
		for coin in coins:
			change_result = self.coin_change(coins, remainder - coin)
			if change_result >= 0 and change_result < minimum:
				minimum = 1 + change_result
		self.cache[remainder] = -1 if minimum == system_max else minimum
		return self.cache[remainder]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		return self.dfs(coins, 0, 0, amount, -1)

	def dfs(self, coins: List[int], idx: int, cnt: int, amount: int, minCnt: int) -> int:
		if amount == 0:
			return cnt
		if idx >= len(coins):
			return -1
		if minCnt > 0 and cnt + amount // coins[idx] + 1 > minCnt:
			return -1
		for i in range(amount // coins[idx], -1, -1):
			res = self.dfs(coins, idx + 1, cnt + i, amount - coins[idx] * i, minCnt)
			if res != -1:
				minCnt = res if minCnt == -1 else min(minCnt, res)
		return minCnt


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		n = len(coins)
		if amount == 0:
			return 0
		if amount < min(coins):
			return -1
		l = min(coins)
		A = [0 for i in range(amount + 1)]
		A[l] = 1
		for i in range(1, amount + 1):
			A[i] = float('inf')
			for coin in coins:
				if i > coin and A[i - coin] > 0:
					A[i] = min(A[i], 1 + A[i - coin])
				elif i == coin:
					A[i] = 1
			if A[i] == float('inf'):
				A[i] = 0
		print(A)
		if A[amount] == 0:
			return -1
		return A[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		count = {}
		for coin in coins:
			count[coin] = 1
		count[0] = 0
		for i in range(1, amount + 1):
			ans = amount + 1
			if i in list(count.keys()):
				continue
			for coin in coins:
				if i - coin > 0 and count[i - coin] != -1:
					ans = min(count[i - coin], ans)
			if ans == amount + 1:
				count[i] = -1
			else:
				count[i] = ans + 1
		return count[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		cnt = [0 for __ in range(amount)]
		return self.coinMake(coins, amount, cnt)

	def coinMake(self, coins, rem, count):
		if rem < 0:
			return -1
		if rem == 0:
			return 0
		if count[rem - 1] != 0:
			return count[rem - 1]
		MIN = 2 ** 32 - 1
		for i in coins:
			res = self.coinMake(coins, rem - i, count)
			if res >= 0 and res < MIN:
				MIN = 1 + res
		count[rem - 1] = -1 if MIN == 2 ** 32 - 1 else MIN
		return count[rem - 1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		mem = {}
		max_amount = 10 ** 4 + 1

		def cc(amount):
			mem[amount] = max_amount
			for coin in coins:
				dif = amount - coin
				if dif == 0:
					mem[amount] = 1
				elif dif > 0:
					if dif not in mem:
						cc(dif)
					mem[amount] = min(mem[amount], mem[dif] + 1)
		cc(amount)
		if mem[amount] == max_amount:
			return -1
		else:
			return mem[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		states = [0] * (amount + 1)
		for s in range(0, amount + 1):
			if s == 0:
				states[s] = 0
			else:
				min_c = 1000000000.0
				for c in coins:
					if c <= s and states[s - c] != -1:
						min_c = min(min_c, 1 + states[s - c])
				if min_c == 1000000000.0:
					states[s] = -1
				else:
					states[s] = min_c
				print(s, states[s])
		return states[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0 or not coins:
			return 0
		minlst = [float('inf')] * (amount + 1)
		n = len(minlst)
		minlst[0] = 0
		for i in range(1, n):
			for denom in coins:
				remainder = i - denom
				if remainder < 0:
					continue
				newsmallest = min(minlst[remainder] + 1, minlst[i])
				minlst[i] = newsmallest
		return -1 if minlst[-1] == float('inf') else minlst[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		s = list()
		s.append(0)
		for i in range(1, amount + 1):
			m = list()
			for j in range(0, len(coins)):
				if i - coins[j] >= 0:
					m.append(s[i - coins[j]])
			mm = [item for item in m if item >= 0]
			if len(mm) == 0:
				s.append(-1)
			else:
				s.append(min(mm) + 1)
		return s[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def my_coinChange(coins, rem, count):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if count[rem - 1] != 0:
				return count[rem - 1]
			my_min = float('inf')
			for coin in coins:
				res = my_coinChange(coins, rem - coin, count)
				if res >= 0 and res < my_min:
					my_min = 1 + res
			count[rem - 1] = -1 if my_min == float('inf') else my_min
			return count[rem - 1]
		if amount < 1:
			return 0
		return my_coinChange(coins, amount, [0] * amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount < 0:
			return -1
		f = [sys.maxsize for i in range(amount + 1)]
		f[0] = 0
		for i in range(1, len(f)):
			for coin in coins:
				if i - coin >= 0 and f[i - coin] != sys.maxsize:
					f[i] = min(f[i], f[i - coin] + 1)
		if f[amount] == sys.maxsize:
			return -1
		return f[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [None for _ in range(amount + 2)]
		dp[amount + 1] = float('inf')
		dp[amount] = 0
		for i in range(amount - 1, -1, -1):
			s = float('inf')
			for c in coins:
				s = min(s, 1 + dp[min(c + i, amount + 1)])
			dp[i] = s
		if dp[0] == float('inf'):
			return -1
		return dp[0]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helper(coins, rem, count):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if count[rem - 1] != 0:
				return count[rem - 1]
			minVal = float('inf')
			for c in coins:
				res = helper(coins, rem - c, count)
				if res >= 0 and res < minVal:
					minVal = 1 + res
			if minVal == float('inf'):
				count[rem - 1] = -1
			else:
				count[rem - 1] = minVal
			return count[rem - 1]
		if amount < 1:
			return 0
		return helper(coins, amount, [0] * amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		result = []
		coins.sort(reverse=True)
		max_sum = 2 ** 31 - 1

		def find_combinations(combination, remain, start):
			nonlocal max_sum
			if remain == 0:
				max_sum = min(max_sum, len(combination))
				return
			elif remain < 0:
				return
			for i in range(start, len(coins)):
				allowed_coins = max_sum - len(combination)
				max_value_can_be_achieved = coins[i] * allowed_coins
				if coins[i] <= remain < max_value_can_be_achieved:
					combination.append(coins[i])
					find_combinations(combination, remain - coins[i], i)
					combination.pop()
		find_combinations([], amount, 0)
		if max_sum == 2 ** 31 - 1:
			return -1
		return max_sum


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def solve(cur):
			if cur in memo:
				return memo[cur]
			if cur == 0:
				return 0
			arr = [float('inf')] * len(coins)
			for (i, coin) in enumerate(coins):
				if cur - coin < 0:
					arr[i] = float('inf')
				else:
					arr[i] = solve(cur - coin) + 1
			ret = min(arr)
			memo[cur] = ret
			return ret
		ans = solve(amount)
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		N = len(coins)
		M = amount
		table = [-1] * (M + 1)
		for j in range(N + 1):
			table[0] = 0
		for m in range(1, M + 1):
			for i in range(N):
				c = coins[i]
				if c > m:
					pass
				elif table[m - c] != -1:
					if table[m] != -1:
						table[m] = min(table[m - c] + 1, table[m])
					else:
						table[m] = table[m - c] + 1
		return table[M]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def dp(t):
			if t in d:
				return d[t]
			res = float('inf')
			for c in coins:
				if t - c >= 0:
					res = min(res, dp(t - c) + 1)
			d[t] = res
			return res
		d = {0: 0}
		x = dp(amount)
		return x if x < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def dfs(remaining):
			nonlocal memo
			if remaining == 0:
				return 0
			if remaining < 0:
				return -1
			if memo[remaining]:
				return memo[remaining]
			res = amount + 1
			for coin in coins:
				count = dfs(remaining - coin)
				if count == -1:
					continue
				res = min(res, 1 + count)
			memo[remaining] = res if res != amount + 1 else -1
			return memo[remaining]
		memo = [None for _ in range(amount + 1)]
		return dfs(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cal = [float('inf') for i in range(amount + 1)]
		for i in range(0, amount + 1):
			for j in range(len(coins)):
				if i == 0:
					cal[i] = 0
				elif coins[j] <= i:
					cal[i] = min(1 + cal[i - coins[j]], cal[i])
		print(cal)
		if cal[amount] == float('inf'):
			return -1
		else:
			return cal[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		dp: List[int] = [0 for _ in range(amount)]
		for i in range(amount):
			for coin in coins:
				if coin > i + 1:
					continue
				if coin == i + 1:
					dp[i] = 1
				elif dp[i - coin] != 0:
					if dp[i] == 0:
						dp[i] = dp[i - coin] + 1
					else:
						dp[i] = min(dp[i], dp[i - coin] + 1)
		return dp[amount - 1] if dp[amount - 1] != 0 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		x = coinCount(coins, amount, {})
		if x == float('inf'):
			return -1
		return x

def coinCount(coins, amount, found):
	if amount < 0:
		return float('inf')
	if amount == 0:
		return 0
	if found.get(amount):
		return found[amount]
	count = 0
	minCount = float('inf')
	for coin in coins:
		if coin == amount:
			return 1
		count = 1 + coinCount(coins, amount - coin, found)
		if count < minCount:
			minCount = count
	found[amount] = minCount
	return minCount


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def opt(v):
			if v == 0:
				return 0
			if v in memo:
				return memo[v]
			result = float('inf')
			for i in coins:
				if v - i >= 0:
					result = min(result, opt(v - i) + 1)
				else:
					continue
			memo[v] = result
			return memo[v]
		memo = {}
		coins = opt(amount)
		if coins == float('inf'):
			return -1
		else:
			return coins


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		seen = {0: 0}

		def helper(coins, amount):
			if amount in seen:
				return seen[amount]
			if amount < 0:
				return -1
			leastCoins = float('Inf')
			for coin in coins:
				next_least = helper(coins, amount - coin)
				if next_least != -1:
					leastCoins = min(leastCoins, 1 + next_least)
			if leastCoins == float('Inf'):
				seen[amount] = -1
				return -1
			else:
				seen[amount] = leastCoins
				return leastCoins
		return helper(coins, amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		memo = {x: amount + 1 for x in range(amount + 1)}
		memo[0] = 0
		for i in range(amount + 1):
			for j in range(len(coins)):
				if coins[j] <= i:
					memo[i] = min(memo[i], 1 + memo[i - coins[j]])
		if memo[amount] < amount + 1:
			return memo[amount]
		else:
			return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = {}
		for c in coins:
			dp[c] = 1
		for i in range(amount + 1):
			for c in coins:
				if dp.get(i - c):
					if not dp.get(i):
						dp[i] = dp[i - c] + 1
					else:
						dp[i] = min(dp[i], dp[i - c] + 1)
		return dp.get(amount, -1)


class Solution:
	IMPOSSIBLE = -1

	def computeMinCoins(self, n: int) -> int:
		if (result := self.memoization.get(n)) is not None:
			return result
		if n == 0:
			result = 0
		else:
			result = Solution.IMPOSSIBLE
			for coin in self.coins:
				if coin > n:
					continue
				if (needed_extra := self.computeMinCoins(n - coin)) != Solution.IMPOSSIBLE:
					possible_result = 1 + needed_extra
					if result == Solution.IMPOSSIBLE or result > possible_result:
						result = possible_result
		self.memoization[n] = result
		return result

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		if amount % coins[0] == 0:
			return amount // coins[0]
		self.coins = coins
		self.memoization = {}
		return self.computeMinCoins(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		dp = [None for _ in range(amount + 1)]
		ret = self.helper(coins, amount, dp)
		return ret if ret != float('inf') else -1

	def helper(self, coins: List[int], amount: int, dp) -> int:
		if amount == 0:
			return 0
		if amount < coins[0]:
			return float('inf')
		ans = float('inf')
		for coin in coins:
			if amount >= coin:
				if amount == coin:
					ans = 0
				else:
					tmp = self.helper(coins, amount - coin, dp) if dp[amount - coin] == None else dp[amount - coin]
					if dp[amount - coin] == None:
						dp[amount - coin] = tmp
					ans = min(ans, tmp)
		return ans + 1 if ans != -1 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def backtrack(tot):
			if tot == 0:
				return 0
			if tot not in memo:
				min_coins = float('inf')
				for coin in coins:
					if coin <= tot:
						cur_count = backtrack(tot - coin) + 1
						min_coins = min(min_coins, cur_count)
				memo[tot] = min_coins
			return memo[tot]
		out = backtrack(amount)
		return -1 if out == float('inf') else out


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memory = {}
		return self._helper(coins, amount, memory)

	def _helper(self, coins, amount, memory):
		if amount < 0:
			return -1
		elif amount == 0:
			return 0
		elif amount in memory:
			return memory[amount]
		potential_values = []
		for coin in coins:
			new_target = amount - coin
			min_coins = self._helper(coins, new_target, memory)
			if min_coins != -1:
				potential_values.append(min_coins)
		if len(potential_values) == 0:
			memory[amount] = -1
		else:
			memory[amount] = min(potential_values) + 1
		return memory[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		d = {0: 0}

		def dfs(left, num):
			if left < 0:
				return -1
			if left in d:
				return d[left]
			min_ans = math.inf
			for each in coins:
				val = dfs(left - each, num + 1)
				if val >= 0:
					min_ans = min(min_ans, val)
			if min_ans == math.inf:
				d[left] = -1
			else:
				d[left] = min_ans + 1
			return d[left]
		return dfs(amount, 0)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] * (amount + 1)
		return self.painful(coins, amount, dp)

	def painful(self, coins: List[int], amount: int, dp: List[int]) -> int:
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		if dp[amount]:
			return dp[amount]
		minCost = math.inf
		for coin in coins:
			res = self.painful(coins, amount - coin, dp)
			if res != -1:
				minCost = min(minCost, 1 + res)
		dp[amount] = minCost if minCost < math.inf else -1
		return minCost if minCost < math.inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helper(amount, minAmounts):
			if amount == 0:
				return 0
			elif amount < 0:
				return math.inf
			if amount in minAmounts:
				return minAmounts[amount]
			minAmount = math.inf
			for coin in coins:
				minAmount = min(minAmount, helper(amount - coin, minAmounts) + 1)
			minAmounts[amount] = minAmount
			return minAmount
		minAmounts = dict()
		x = helper(amount, minAmounts)
		if x == math.inf:
			return -1
		return x


class Solution:

	def __init__(self):
		self.cache = dict()
		self.coin_set = set()

	def helper(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if amount in self.cache:
			return self.cache[amount]
		if amount in self.coin_set:
			return 1
		potentials = [float('inf')]
		for coin in coins:
			if amount > coin:
				potentials.append(self.helper(coins, amount - coin))
		res = 1 + min(potentials)
		self.cache[amount] = res
		return res

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.coin_set = set(coins)
		coins = sorted(coins, reverse=True)
		res = self.helper(coins, amount)
		if res == float('inf'):
			return -1
		return res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		cache = {}

		def rec(amount):
			if amount == 0:
				return 0
			if amount in cache:
				return cache[amount]
			val = float('inf')
			for coin in coins:
				if amount - coin >= 0:
					val = min(val, 1 + rec(amount - coin))
			cache[amount] = val
			return val
		ans = rec(amount)
		return ans if ans != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cache = {0: 0}

		def recurse(i):
			if i in cache:
				return cache[i]
			n = i + 1
			for coin in coins:
				curr = 0
				if i >= coin:
					next_amount = recurse(i - coin)
					if next_amount >= 0:
						curr = 1 + next_amount
				if curr > 0:
					n = min(n, curr)
			result = -1 if n == i + 1 else n
			cache[i] = result
			return result
		return recurse(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helper(coins, amount, dp):
			if amount < 0:
				return float('inf')
			if amount == 0:
				return 0
			if amount in dp:
				return dp[amount]
			ans = []
			for i in range(len(coins)):
				use_ci = 1 + helper(coins, amount - coins[i], dp)
				ans.append(use_ci)
			dp[amount] = min(ans)
			return dp[amount]
		if amount <= 0:
			return 0
		dp = {}
		result = helper(coins, amount, dp)
		return -1 if result == float('inf') else result


from collections import defaultdict

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def coin_change_for_amount(coins, amount):
			nonlocal count_amount
			if amount < 0:
				return -1
			if amount == 0:
				return 0
			if count_amount[amount] != float('inf'):
				return count_amount[amount]
			min_coins_amt = float('inf')
			for coin in coins:
				min_coins_amt_coin = coin_change_for_amount(coins, amount - coin)
				if 0 <= min_coins_amt_coin < min_coins_amt:
					min_coins_amt = min_coins_amt_coin + 1
			count_amount[amount] = -1 if min_coins_amt == float('inf') else min_coins_amt
			return count_amount[amount]
		if amount <= 0:
			return 0
		count_amount = [float('inf')] * (amount + 1)
		coin_change_for_amount(coins, amount)
		return count_amount[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coinsNeeded = {}
		coinsNeeded[0] = 0
		for n in coins:
			coinsNeeded[n] = 1

		def findMinCoins(amount):
			if amount < 0:
				return float('inf')
			if amount in coinsNeeded:
				return coinsNeeded[amount]
			for n in coins:
				coinsUsed = 1 + findMinCoins(amount - n)
				if amount in coinsNeeded:
					coinsNeeded[amount] = min(coinsUsed, coinsNeeded[amount])
				else:
					coinsNeeded[amount] = coinsUsed
			return coinsNeeded[amount]
		findMinCoins(amount)
		if coinsNeeded[amount] == float('inf'):
			return -1
		return coinsNeeded[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = {}

		def recursion(S):
			if S == 0:
				return 0
			if S < 0:
				return float('inf')
			if S in dp:
				return dp[S]
			x = float('inf')
			for coin in coins:
				x = min(x, 1 + recursion(S - coin))
			dp[S] = x
			return x
		res = recursion(amount)
		if res == float('inf'):
			return -1
		return res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		l = [amount + 1] * (amount + 1)
		for i in range(len(l)):
			if i == 0:
				l[i] = 0
			elif all((i < c for c in coins)):
				l[i] = -1
			else:
				for j in range(len(coins)):
					if i >= coins[j]:
						num = i - coins[j]
						if num > 0 and l[num] == -1:
							if l[i] != amount + 1:
								continue
							else:
								l[i] = -1
						else:
							comb = l[num] + 1
							if l[i] == -1:
								l[i] = amount + 1
							if l[i] >= comb:
								l[i] = comb
		return l[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins_sorted = list(sorted(coins, reverse=True))
		memo = {}

		def choose(amount):
			if amount in memo:
				return memo[amount]
			if amount < 0:
				return -1
			if amount == 0:
				return 0
			memo[amount] = -1
			for c in coins_sorted:
				if (ret := choose(amount - c)) >= 0:
					if memo[amount] != -1:
						memo[amount] = min(memo[amount], ret + 1)
					else:
						memo[amount] = ret + 1
			return memo[amount]
		return choose(amount)


class Solution:
	IMPOSSIBLE = -1

	def computeMinCoins(self, n: int) -> int:
		if n in self.memoization:
			return self.memoization.get(n)
		if n == 0:
			result = 0
		else:
			result = Solution.IMPOSSIBLE
			for coin in self.coins:
				if coin > n:
					continue
				coins_extra = self.computeMinCoins(n - coin)
				if coins_extra == Solution.IMPOSSIBLE:
					continue
				plausible_result = 1 + coins_extra
				if result == Solution.IMPOSSIBLE or result > plausible_result:
					result = plausible_result
		self.memoization[n] = result
		return result

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		if amount % coins[0] == 0:
			return amount // coins[0]
		self.coins = coins
		self.memoization = {}
		return self.computeMinCoins(amount)


import math
from functools import lru_cache

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins or amount < 0:
			return -1
		stack = [(0, 0)]
		answer = math.inf
		sortedCoins = sorted(coins)
		visited = set()
		while stack:
			node = stack.pop()
			(sum, coinCount) = node
			if node in visited:
				pass
			elif coinCount >= answer:
				pass
			elif sum == amount:
				answer = min(answer, coinCount)
			elif sum > amount:
				pass
			else:
				for c in sortedCoins:
					if sum + c <= amount and amount < sum + c * (answer - coinCount):
						stack.append((sum + c, coinCount + 1))
			visited.add(node)
		if answer == math.inf:
			return -1
		else:
			return answer


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cache = dict()

		def recursiveChange(amount):
			if amount == 0:
				return 0
			if amount < 0:
				return -1
			if amount in cache:
				return cache[amount]
			min_val = float('inf')
			for coin_val in coins:
				combination = recursiveChange(amount - coin_val)
				if combination != -1:
					min_val = min(min_val, combination + 1)
			cache[amount] = min_val
			return min_val
		ans = recursiveChange(amount)
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = [None] * amount
		dp[0] = 1 if 1 in coins else -1
		for i in range(1, amount):
			min_req = float('inf')
			for c in coins:
				if (i + 1) % c == 0:
					min_req = min(min_req, (i + 1) // c)
				elif (i + 1) // c > 0 and dp[i - c] != -1:
					min_req = min(min_req, dp[i - c] + 1)
			if min_req == float('inf'):
				dp[i] = -1
			else:
				dp[i] = min_req
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		self.coins = sorted(coins, reverse=True)
		self.count = {}
		return self.helper(amount)

	def helper(self, rem):
		if rem < 0:
			return -1
		if rem == 0:
			return 0
		if rem in self.count:
			return self.count[rem]
		min_count = 1000000000
		for coin in self.coins:
			res = self.helper(rem - coin)
			if res >= 0 and res < min_count:
				min_count = res + 1
			if min_count == 1000000000:
				self.count[rem] = -1
			else:
				self.count[rem] = min_count
		return self.count[rem]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = [0] * (amount + 1)
		return self.dfs(coins, amount, memo)

	def dfs(self, coins: List[int], amount: int, memo: List[int]) -> int:
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		if memo[amount] != 0:
			return memo[amount]
		minCoins = math.inf
		for coin in coins:
			res = self.dfs(coins, amount - coin, memo) + 1
			if res > 0:
				minCoins = min(minCoins, res)
		memo[amount] = minCoins if minCoins < math.inf else -1
		return minCoins if minCoins < math.inf else -1


import sys

class Solution:

	def helper(self, coin_sum, coins, memo):
		if coin_sum == 0:
			return 0
		if coin_sum < 0:
			return sys.maxsize
		if memo[coin_sum - 1] != 0:
			return memo[coin_sum - 1]
		res = sys.maxsize
		for c in coins:
			res = min(res, self.helper(coin_sum - c, coins, memo) + 1)
		memo[coin_sum - 1] = res
		return res

	def coinChange(self, coins, amount):
		memo = [0] * amount
		res = self.helper(amount, coins, memo)
		return -1 if res == sys.maxsize else res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [None for _ in range(amount + 1)]

		def fewest_num(amount, dp):
			if dp[amount] is not None:
				return dp[amount]
			if amount == 0:
				min_num = 0
			elif amount < min(coins):
				min_num = float('inf')
			elif amount in set(coins):
				min_num = 1
			else:
				min_num = float('inf')
				for coin in coins:
					if amount - coin >= 0:
						num = fewest_num(amount - coin, dp)
						min_num = min(min_num, num)
				min_num += 1
			dp[amount] = min_num
			return min_num
		min_num = fewest_num(amount, dp)
		if min_num == float('inf'):
			return -1
		return min_num


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.memo = {0: 0}
		coins.sort()
		self.getMinCoins(coins, amount)
		if self.memo[amount] == float('inf'):
			return -1
		return self.memo[amount]

	def getMinCoins(self, coins, amount):
		if amount in self.memo:
			return self.memo[amount]
		minCoins = float('inf')
		for coin in coins:
			if amount - coin < 0:
				break
			currCoins = self.getMinCoins(coins, amount - coin) + 1
			minCoins = min(minCoins, currCoins)
		self.memo[amount] = minCoins
		return self.memo[amount]


class Solution:

	def helper(self, amount: int) -> int:
		if amount in list(self.cache.keys()):
			return self.cache[amount]
		counts = []
		for coin in self.coins:
			if amount - coin > 0:
				counts.append(self.helper(amount - coin) + 1)
			elif amount - coin == 0:
				counts.append(1)
				break
		if counts == []:
			self.cache[amount] = sys.maxsize
		else:
			self.cache[amount] = min(counts)
		return self.cache[amount]

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.coins = coins
		if amount == 0:
			return 0
		self.cache = {}
		res = self.helper(amount)
		return res if res < 100000000 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		value = [-1] * (amount + 1)
		value[0] = 0
		for j in range(amount + 1):
			for i in range(len(coins)):
				if j > coins[i]:
					if value[j - coins[i]] != -1:
						if value[j] == -1:
							value[j] = value[j - coins[i]] + 1
						else:
							value[j] = min(value[j], value[j - coins[i]] + 1)
				if j == coins[i]:
					value[j] = 1
		print(value)
		return value[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		d = {}
		ans = self.helper(coins, amount, d)
		if ans == 100000000:
			return -1
		return ans

	def helper(self, coins, amount, d):
		if amount == 0:
			return 0
		ans = 100000000
		for i in range(len(coins) - 1, -1, -1):
			if coins[i] <= amount:
				if amount - coins[i] in d:
					sub_ans = d[amount - coins[i]]
				else:
					sub_ans = 1 + self.helper(coins, amount - coins[i], d)
					d[amount - coins[i]] = sub_ans
				ans = min(ans, sub_ans)
		return ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort(reverse=True)
		memo = {}

		def dfs(step, rest_amount):
			if rest_amount < 0:
				return -1
			if rest_amount == 0:
				return 0
			if rest_amount in memo:
				return memo[rest_amount]
			min_steps = math.inf
			for coin in coins:
				rest = rest_amount - coin
				res = dfs(step + 1, rest)
				if res >= 0:
					min_steps = min(min_steps, res)
			memo[rest_amount] = min_steps + 1 if min_steps != math.inf else -1
			return memo[rest_amount]
		res = dfs(0, amount)
		return res


class Solution:

	def coinChange2(self, coins: List[int], amount: int, count) -> int:
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if count[amount - 1] != 0:
			return count[amount - 1]
		min = 100000000000
		for (i, c) in enumerate(sorted(coins)[::-1]):
			ret = self.coinChange2(coins, amount - c, count)
			if ret >= 0 and ret < min:
				min = 1 + ret
		if min == 100000000000:
			count[amount - 1] = -1
		else:
			count[amount - 1] = min
		return count[amount - 1]

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		return self.coinChange2(coins, amount, [0] * amount)


class Solution(object):

	def __init__(self):
		self.mem = {0: 0}

	def getMinCoins(self, coins, amount):
		if amount in self.mem:
			return self.mem[amount]
		minCoins = float('inf')
		for c in coins:
			if amount - c < 0:
				break
			numCoins = self.getMinCoins(coins, amount - c) + 1
			minCoins = min(numCoins, minCoins)
		self.mem[amount] = minCoins
		return minCoins

	def coinChange(self, coins, amount):
		minCoins = self.getMinCoins(sorted(coins), amount)
		if minCoins == float('inf'):
			return -1
		return minCoins


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = dict()

		def recurse(amount, index):
			if amount == 0:
				return 0
			if amount in memo:
				return memo[amount]
			minCoins = float('inf')
			for coin in coins:
				if amount - coin >= 0:
					response = recurse(amount - coin, 0)
					if response != -1:
						minCoins = min(minCoins, response + 1)
			memo[amount] = minCoins if minCoins != float('inf') else -1
			return memo[amount]
		return recurse(amount, 0)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		f = [float('inf') for i in range(amount + 1)]
		f[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				if i - coin >= 0 and f[i - coin] != float('inf'):
					f[i] = min(f[i], f[i - coin] + 1)
		if f[-1] == float('inf'):
			return -1
		return f[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def backtrack(memo, curr=amount):
			if curr == 0:
				return 0
			if memo.get(curr):
				return memo[curr]
			minimum = math.inf
			for coin in coins:
				if curr - coin < 0:
					continue
				res = backtrack(memo, curr - coin)
				minimum = min(res, minimum)
			minimum = minimum if minimum == math.inf else minimum + 1
			memo[curr] = minimum
			return minimum
		ans = backtrack(memo)
		if ans == math.inf:
			return -1
		return ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cache = {}
		coins = sorted(coins, reverse=True)

		def helper(coins, amount, cache):
			if amount == 0:
				return 0
			elif amount in cache:
				return cache[amount]
			cache[amount] = float('inf')
			for c in coins:
				if amount - c >= 0:
					cache[amount] = min(cache[amount], helper(coins, amount - c, cache) + 1)
			return cache[amount]
		if amount == 0:
			return 0
		if min(coins) > amount:
			return -1
		ans = helper(coins, amount, {})
		return ans if ans != float('inf') else -1


class Solution:

	def helper(self, coins, amount, total, count, mem):
		if total > amount:
			return
		if total == amount:
			if total not in mem:
				mem[total] = count
			else:
				mem[total] = min(mem[total], count)
			return
		for c in coins:
			if total + c not in mem or mem[total + c] > count + 1:
				mem[total + c] = count + 1
				self.helper(coins, amount, total + c, count + 1, mem)
		return

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		if amount < min(coins):
			return -1
		mem = {}
		coins.sort(reverse=True)
		self.helper(coins, amount, 0, 0, mem)
		if amount in mem:
			return mem[amount]
		else:
			return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		fewest_coins = [0 for j in range(amount + 1)]
		for j in range(1, amount + 1):
			fewest_coins[j] = float('inf')
			for coin_i in range(len(coins)):
				if coins[coin_i] == j:
					fewest_coins[j] = 1
					break
				elif coins[coin_i] < j:
					if fewest_coins[j - coins[coin_i]] > 0:
						fewest_coins[j] = min(fewest_coins[j], fewest_coins[j - coins[coin_i]] + 1)
			if fewest_coins[j] == float('inf'):
				fewest_coins[j] = -1
		return fewest_coins[-1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		M = [[0 for j in range(amount + 1)] for i in range(len(coins) + 1)]
		for j in range(1, amount + 1):
			M[0][j] = 1000000
		for i in range(1, len(coins) + 1):
			for j in range(1, amount + 1):
				if j >= coins[i - 1]:
					M[i][j] = min(1 + M[i][j - coins[i - 1]], M[i - 1][j])
				else:
					M[i][j] = M[i - 1][j]
		return M[-1][-1] if M[-1][-1] < 1000000 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		matrix = [[0 for i in range(amount + 1)] for j in range(len(coins) + 1)]
		for i in range(len(matrix)):
			matrix[i][0] = 0
		for i in range(1, amount + 1):
			matrix[0][i] = sys.maxsize
		for i in range(1, len(matrix)):
			for j in range(len(matrix[0])):
				if j < coins[i - 1]:
					matrix[i][j] = matrix[i - 1][j]
				else:
					matrix[i][j] = min(matrix[i - 1][j], 1 + matrix[i][j - coins[i - 1]])
		if matrix[-1][-1] == sys.maxsize:
			return -1
		return matrix[-1][-1]


class Solution:

	def __init__(self):
		self.counts = {}

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if amount in self.counts:
			return self.counts[amount]
		minCoins = -1
		for val in coins:
			numCoins = self.coinChange(coins, amount - val)
			if numCoins != -1:
				if minCoins == -1:
					minCoins = 1 + numCoins
				else:
					minCoins = min(minCoins, 1 + numCoins)
		self.counts[amount] = minCoins
		return minCoins


class Solution:

	def coinChange2(self, coins: List[int], amount: int) -> int:
		impossible = amount + 1
		cnts = [impossible] * impossible
		cnts[0] = 0
		for coin in coins:
			for x in range(coin, impossible):
				cnts[x] = min(cnts[x], cnts[x - coin] + 1)
		if cnts[amount] >= impossible:
			return -1
		return cnts[amount]

	def coinChange(self, coins: List[int], amount: int) -> int:
		impossible = amount + 1
		self.cnts = [0] * impossible

		def createCoins(total: int):
			if total == 0:
				return 0
			if self.cnts[total] != 0:
				return self.cnts[total]
			minCnt = impossible
			for coin in coins:
				if total - coin < 0:
					continue
				cnt = createCoins(total - coin) + 1
				minCnt = min(cnt, minCnt)
			self.cnts[total] = minCnt
			return minCnt
		retV = createCoins(amount)
		if retV >= impossible:
			return -1
		return retV


class Solution:

	def coinChange(self, coin: List[int], amount: int) -> int:
		dp = [[9999999 for _ in range(amount + 1)] for _ in range(len(coin) + 1)]
		for i in range(1, len(coin) + 1):
			dp[i][0] = 0
		for i in range(1, len(coin) + 1):
			for j in range(1, amount + 1):
				if j >= coin[i - 1]:
					dp[i][j] = min(dp[i][j - coin[i - 1]] + 1, dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[-1][-1] == 9999999:
			return -1
		return dp[-1][-1]


class Solution:

	def coinChangeDynamic(self, coins: List[int], amount: int, memory_dict: dict) -> int:
		if amount < 0:
			return -1
		elif amount == 0:
			return 0
		elif memory_dict.get(amount) is None:
			recursive_call_output = []
			for coin_val in coins:
				recursive_call_output.append(self.coinChangeDynamic(coins, amount - coin_val, memory_dict))
			min_num_coins = float('inf')
			for num_coins in recursive_call_output:
				if num_coins >= 0 and num_coins < min_num_coins:
					min_num_coins = num_coins
			if min_num_coins == float('inf'):
				memory_dict[amount] = -1
				return -1
			else:
				memory_dict[amount] = min_num_coins + 1
				return min_num_coins + 1
		else:
			return memory_dict[amount]

	def coinChange(self, coins: List[int], amount: int) -> int:
		return self.coinChangeDynamic(coins, amount, {})


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [[0 for i in range(amount + 1)] for i in range(len(coins))]
		col = amount + 1
		for i in range(len(coins)):
			for j in range(1, col):
				if i == 0:
					r = i
					c = j - coins[i]
					if c < 0 or dp[r][c] == -1:
						dp[i][j] = -1
					else:
						dp[i][j] = dp[r][c] + 1
				else:
					incIndex = j - coins[i]
					if incIndex < 0 or dp[i][incIndex] == -1:
						dp[i][j] = dp[i - 1][j]
					else:
						dp[i][j] = dp[i][incIndex] + 1
						if dp[i - 1][j] != -1:
							dp[i][j] = min(dp[i - 1][j], dp[i][incIndex] + 1)
		return dp[len(coins) - 1][col - 1]


import math

class Solution:
	trellis = None

	def coinChange(self, coins: List[int], amount: int) -> int:
		if self.trellis == None:
			self.trellis = [math.inf] * (amount + 1)
			self.trellis[0] = 0
		if self.trellis[amount] != math.inf:
			return self.trellis[amount]
		if amount < 0:
			return -1
		minVal = math.inf
		for coin in coins:
			required = amount - coin
			if required < 0:
				continue
			val = self.trellis[required] if self.trellis[required] != math.inf else self.coinChange(coins, required)
			if val == -1:
				continue
			else:
				minVal = min(minVal, val + 1)
		if minVal == math.inf:
			minVal = -1
		self.trellis[amount] = min(self.trellis[amount], minVal)
		return minVal


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		arr = coins
		w = amount
		n = len(arr)
		t = [[0] * (w + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(w + 1):
				if j == 0 and i != 0:
					t[i][j] = 0
				if i == 1 and j != 0:
					t[i][j] = int(j / arr[i - 1]) if j % arr[i - 1] == 0 else math.inf
		for i in range(2, n + 1):
			for j in range(1, w + 1):
				if arr[i - 1] <= j:
					t[i][j] = min(t[i][j - arr[i - 1]] + 1, t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return -1 if t[n][w] == math.inf else t[n][w]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def coinChangeHelper(coins, amount, memoisation={}):
			if amount == 0:
				return 0
			if amount < 0:
				return float('inf')
			if amount in memoisation:
				return memoisation[amount]
			min_coins_used = float('inf')
			for i in range(len(coins) - 1, -1, -1):
				min_coins_used = min(1 + coinChangeHelper(coins, amount - coins[i], memoisation), min_coins_used)
			memoisation[amount] = min_coins_used
			return min_coins_used
		result = coinChangeHelper(coins, amount)
		return result if result != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def dp(m):
			if m in coins:
				return 1
			if m == 0:
				return 0
			if m < 0:
				return float('inf')
			if m not in memo:
				ans = float('inf')
				for v in coins:
					ans = min(1 + dp(m - v), ans)
				memo[m] = ans
			return memo[m]
		return dp(amount) if dp(amount) != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coinsCount = dict()
		for i in range(1, amount + 1):
			coinsCount[i] = 9999
		coinsCount[0] = 0
		for i in range(1, amount + 1):
			for icoin in range(0, len(coins)):
				curDenom = coins[icoin]
				difference = i - curDenom
				if difference >= 0:
					coinsCount[i] = min(1 + coinsCount[difference], coinsCount[i])
				elif difference == 0:
					coinsCount[i] += 1
		if coinsCount[amount] != 9999:
			return coinsCount[amount]
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		self.dp = {}
		min_ = sys.maxsize
		for coin in coins:
			if amount - coin >= 0:
				min_ = min(min_, 1 + self.change(amount - coin, coins))
		if min_ == sys.maxsize:
			return -1
		return min_

	def change(self, amount, coins):
		if amount in self.dp:
			return self.dp[amount]
		if amount == 0:
			self.dp[amount] = 0
			return 0
		if amount in coins:
			self.dp[amount] = 1
			return 1
		min_ = sys.maxsize
		for coin in coins:
			if amount - coin >= 0:
				min_ = min(min_, 1 + self.change(amount - coin, coins))
		self.dp[amount] = min_
		return min_


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		N = [0 for i in range(amount + 1)]
		N[0] = 0
		for i in range(1, amount + 1):
			temp = [i - j for j in coins]
			history = [N[temp2] for temp2 in temp if temp2 <= i and temp2 >= 0 and (N[temp2] != -1)]
			if len(history) == 0:
				N[i] = -1
			else:
				N[i] = 1 + min([N[temp2] for temp2 in temp if temp2 <= i and temp2 >= 0 and (N[temp2] != -1)])
		return N[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		round = 0
		d = set([0])
		while d or round == 0:
			round += 1
			d = set([coin + s for coin in coins for s in d if coin + s <= amount and coin + s not in d])
			if amount in d:
				return round
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [-1 for i in range(amount + 1)]
		dp[0] = 0
		for i in range(amount):
			mn = math.inf
			pos = False
			for c in coins:
				if i + 1 >= c and dp[i - c + 1] >= 0:
					pos = True
					mn = min(mn, dp[i + 1 - c] + 1)
			if pos:
				dp[i + 1] = mn
		return dp[-1]


class Solution:
	memory = {}

	def numCoins(self, coins, amount):
		if amount in self.memory:
			return self.memory[amount]
		if amount == 0:
			return 0
		ncarr = []
		carr = []
		for c in coins:
			if amount >= c:
				nnc = self.numCoins(coins, amount - c)
				ncarr.append(nnc + 1)
				carr.append(c)
		if len(ncarr) > 0:
			nc = min(ncarr)
			self.memory[amount] = nc
			return nc
		else:
			return float('inf')

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.memory = {}
		nc = self.numCoins(coins, amount)
		if nc == float('inf'):
			return -1
		return nc


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		n = len(coins)
		dp = [[float('inf') for _ in range(amount + 1)] for _ in range(n)]
		for r in range(n):
			dp[r][0] = 0
		for a in range(1, amount + 1):
			(div, mod) = divmod(a, coins[0])
			if mod == 0:
				dp[0][a] = div
		for i in range(1, n):
			for a in range(1, amount + 1):
				if a - coins[i] >= 0:
					dp[i][a] = min(dp[i][a - coins[i]] + 1, dp[i - 1][a])
				else:
					dp[i][a] = dp[i - 1][a]
		return dp[-1][-1] if dp[-1][-1] != float('inf') else -1


import sys

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		res = self.helper(sorted(coins, reverse=True), amount, {})
		if res == float('inf'):
			return -1
		return res

	def helper(self, coins, amount, dAmounts):
		if amount < 0:
			return float('inf')
		if amount == 0:
			return 0
		if amount in dAmounts:
			return dAmounts[amount]
		for c in coins:
			pathCount = 1 + self.helper(coins, amount - c, dAmounts)
			dAmounts[amount] = min(dAmounts.get(amount, pathCount), pathCount)
		return dAmounts[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('Inf') for _ in range(amount + 1)]
		dp[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				if i >= coin and dp[i - coin] != float('Inf'):
					dp[i] = min(dp[i], dp[i - coin] + 1)
		if dp[amount] == float('Inf'):
			return -1
		return dp[amount]


INF = 100000000000000000

def hashIntArr(i_arr):
	return '-'.join(list(map(str, i_arr)))

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		mc = [[0 if j == 0 else INF for j in range(amount + 1)] for _ in range(len(coins) + 1)]
		for c in range(1, len(coins) + 1):
			coin_value = coins[c - 1]
			for a in range(1, amount + 1):
				if coin_value <= a:
					mc[c][a] = min(1 + mc[c][a - coin_value], mc[c - 1][a])
				else:
					mc[c][a] = mc[c - 1][a]
		min_coins = mc[len(coins)][amount]
		return min_coins if min_coins < INF else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		n = len(coins)
		t = [[float('inf') - 1] * (amount + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			t[i][0] = 0
		for j in range(amount + 1):
			t[0][j] = float('inf') - 1
			if j % coins[0] == 0:
				t[1][j] = j // coins[0]
			else:
				t[1][j] = float('inf') - 1
		for i in range(1, n + 1):
			for j in range(1, amount + 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]
		return t[n][amount] if t[n][amount] != float('inf') else -1


class Solution:

	def __init__(self):
		self.memo = {}

	def coinChange(self, coins: List[int], amount: int) -> int:
		ans = self.helper(coins, amount)
		if ans == float('inf'):
			return -1
		return ans

	def helper(self, coins, remaining):
		if remaining == 0:
			return 0
		if remaining < 0:
			return float('inf')
		if remaining in self.memo:
			return self.memo[remaining]
		self.memo[remaining] = min([self.helper(coins, remaining - i) for i in coins[::-1]]) + 1
		return self.memo[remaining]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.coins = coins
		self.amount_dict = {0: 0}
		for coin in coins:
			self.amount_dict[coin] = 1
		return self.coinChangeHelp(amount)

	@lru_cache
	def coinChangeHelp(self, amount: int) -> int:
		if amount < 0:
			return -1
		if amount in self.amount_dict:
			return self.amount_dict[amount]
		max_coin = amount + 1
		for coin in self.coins:
			cur_coin = self.coinChangeHelp(amount - coin)
			if cur_coin >= 0:
				max_coin = min(max_coin, cur_coin + 1)
		max_coin = max_coin if max_coin != amount + 1 else -1
		self.amount_dict[amount] = max_coin
		return max_coin


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0]
		length = len(coins)
		for i in range(1, amount + 1):
			dp += [9999]
			for j in range(length):
				if i >= coins[j] and dp[int(i - coins[j])] != 9999:
					dp[i] = min(dp[i], dp[int(i - coins[j])] + 1)
		if dp[amount] == 9999:
			return -1
		return dp[amount]


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		best_so_far = math.inf

		def rec(C, A, used):
			nonlocal best_so_far
			if A == 0:
				best_so_far = min(best_so_far, used)
			elif C:
				for i in range(A // C[-1], -1, -1):
					if (best_so_far - used) * C[-1] >= A:
						rec(C[:-1], A - i * C[-1], used + i)
		rec(coins, amount, 0)
		return best_so_far if best_so_far != math.inf else -1


import math
from functools import lru_cache

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		result = self.recurse(amount, tuple(coins))
		if result == math.inf:
			result = -1
		return result

	@lru_cache(maxsize=None)
	def recurse(self, amount: int, coins: tuple) -> int:
		if amount < 0:
			return math.inf
		elif amount == 0:
			return 0
		elif amount in coins:
			return 1
		else:
			least = math.inf
			for c in coins:
				val = self.recurse(amount - c, coins)
				least = min(least, val)
			return least + 1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def helper(coins, rem, counts):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if counts[rem - 1] != 0:
				return counts[rem - 1]
			min_val = float('inf')
			for coin in coins:
				res = helper(coins, rem - coin, counts)
				if res >= 0 and res < min_val:
					min_val = res + 1
				if min_val == float('inf'):
					counts[rem - 1] = -1
				else:
					counts[rem - 1] = min_val
			return counts[rem - 1]
		if amount < 1:
			return 0
		return helper(coins, amount, [0] * amount)


class Solution:

	def coinChange(self, coins: List[int], target: int) -> int:
		table = [[float('inf') for _ in range(target + 1)] for _ in range(len(coins) + 1)]
		for i in range(len(coins) + 1):
			table[i][0] = 0
		for i in range(1, len(coins) + 1):
			for j in range(target + 1):
				if coins[i - 1] <= j:
					a = 1 + table[i][j - coins[i - 1]]
				else:
					a = float('inf')
				b = table[i - 1][j]
				if a <= b:
					table[i][j] = a
				else:
					table[i][j] = b
		return table[-1][-1] if table[-1][-1] != float('inf') else -1


class Solution:
	cache = {}

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.cache = {}
		return self.solve(coins, amount)

	def solve(self, coins, amount):
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		if amount in self.cache:
			return self.cache[amount]
		best = -1
		for c in coins:
			add = self.solve(coins, amount - c)
			if add != -1:
				if best == -1:
					best = add + 1
				else:
					best = min(best, add + 1)
		self.cache[amount] = best
		return best


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		d = {}
		for v in coins:
			d[v] = True
		min_coin = coins[-1]
		if not coins or not amount:
			return 0
		if len(coins) == 1:
			if amount % coins[0] == 0:
				return int(amount / coins[0])
			else:
				return -1
		self.memo = {}
		return self.fewest(coins, amount, d, min_coin)

	def fewest(self, coins, amount, d_value, min_coin):
		if amount in self.memo:
			return self.memo[amount]
		if amount in d_value:
			return 1
		elif amount < min_coin:
			return -1
		_min = float('inf')
		for v in coins:
			ret = self.fewest(coins, amount - v, d_value, min_coin)
			if ret > 0:
				_min = min(_min, ret + 1)
		_min = -1 if _min == float('inf') else _min
		self.memo[amount] = _min
		return _min


class Solution:

	def coinChange(self, coins, amount):
		n = len(coins)
		dp = [[math.inf for _ in range(amount + 1)] for _ in range(n)]
		for (i, coin) in enumerate(coins):
			for t in range(amount + 1):
				if t == 0:
					dp[i][t] = 0
				if i > 0:
					dp[i][t] = dp[i - 1][t]
				if t >= coin:
					dp[i][t] = min(dp[i][t], dp[i][t - coin] + 1)
		return -1 if dp[n - 1][amount] == math.inf else dp[n - 1][amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp_table = [float('inf')] * (amount + 1)
		return self.dp(dp_table, coins, amount)

	def dp(self, dp_table: [float], coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		if dp_table[amount] != float('inf'):
			return dp_table[amount]
		res = float('inf')
		for coin in coins:
			subpb = self.dp(dp_table, coins, amount - coin)
			if subpb == -1:
				continue
			res = min(res, subpb + 1)
		dp_table[amount] = res if res != float('inf') else -1
		return dp_table[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		state = [float('inf')] * amount
		if amount < 1:
			return 0
		max_coin = 0
		for c in coins:
			max_coin = max(c, max_coin)
			if c <= amount:
				state[c - 1] = 1
		for i in range(amount):
			for c in coins:
				if i - c >= 0:
					state[i] = min(state[i - c] + 1, state[i])
		return state[-1] if state[-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		dp = [0] * (amount + 1)
		for item in range(amount + 1):
			if item < coins[0] and item != 0:
				dp[item] = -1
			elif item == 0:
				dp[item] = 0
		if amount < coins[0] and amount == 0:
			return 0
		elif amount < coins[0]:
			return -1
		for i in range(coins[0], amount + 1):
			count = 0
			for j in coins:
				if i - j < 0:
					break
				elif dp[i - j] != -1:
					count += 1
			if count > 0:
				dp[i] = math.ceil(i / coins[0])
				for j in coins:
					if i - j < 0:
						break
					elif dp[i - j] == -1:
						continue
					else:
						dp[i] = min(dp[i], 1 + dp[i - j])
			else:
				dp[i] = -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		self.coins = coins
		self.count = {}
		self.recur_count = 0
		ans = self.helper(amount)
		return ans

	def helper(self, rem):
		self.recur_count += 1
		if rem < 0:
			return -1
		if rem == 0:
			return 0
		if rem in self.count:
			return self.count[rem]
		min_count = 1000000000
		for coin in self.coins:
			res = self.helper(rem - coin)
			if res >= 0 and res < min_count:
				min_count = res + 1
			if min_count == 1000000000:
				self.count[rem] = -1
			else:
				self.count[rem] = min_count
		return self.count[rem]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			for coin in coins[::-1]:
				j = i - coin
				if j < 0 or dp[j] == -1:
					continue
				if dp[i] == -1:
					dp[i] = dp[j] + 1
				else:
					dp[i] = min(dp[i], dp[j] + 1)
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = dict()

		def dp(n):
			if n in memo:
				return memo[n]
			if n == 0:
				return 0
			if n < 0:
				return -1
			res = 1000
			for coin in coins:
				if dp(n - coin) == -1:
					continue
				res = min(res, 1 + dp(n - coin))
			memo[n] = res if res != 1000 else -1
			return memo[n]
		return dp(amount)


class Solution:
	memory = {}

	def numCoins(self, coins, amount):
		if amount in self.memory:
			return self.memory[amount]
		nc = float('inf')
		for c in coins:
			if amount >= c:
				nnc = self.numCoins(coins, amount - c)
				nc = min(nc, nnc + 1)
		self.memory[amount] = nc
		return nc

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.memory = {}
		self.memory[0] = 0
		for c in coins:
			self.memory[c] = 1
		nc = self.numCoins(coins, amount)
		if nc == float('inf'):
			return -1
		return nc


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = {}

		def dfs(amount, path):
			if amount < 0:
				return float('inf')
			if amount == 0:
				return 0
			if amount in memo:
				return memo[amount]
			ans = float('inf')
			for i in coins:
				r = dfs(amount - i, path + 1)
				if r != float('inf'):
					ans = min(ans, r + 1)
			memo[amount] = ans
			return ans
		ret = dfs(amount, 0)
		return ret if ret != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(None)
		def dfs(amt, idx):
			if idx < 0:
				if amt == 0:
					return 0
				else:
					return float('inf')
			if amt < 0:
				return float('inf')
			if amt == coins[idx]:
				return 1
			return min(dfs(amt - coins[idx], idx) + 1, dfs(amt, idx - 1))
		res = dfs(amount, len(coins) - 1)
		return res if res < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		tracker = [float('inf') for i in range(amount)]
		res = self.coinChange_helper(coins, amount, tracker)
		print(tracker)
		if tracker[-1] == float('inf'):
			return -1
		return res

	def coinChange_helper(self, coins: List[int], amount: int, tracking: List[int]) -> int:
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if tracking[amount - 1] != float('inf'):
			return tracking[amount - 1]
		lowest = float('inf')
		for i in range(len(coins)):
			result = self.coinChange_helper(coins, amount - coins[i], tracking)
			if result >= 0 and result + 1 < lowest:
				lowest = result + 1
		tracking[amount - 1] = lowest if lowest != float('inf') else -1
		return tracking[amount - 1]


class Solution:

	def do_du_tab(self, coins, amount):
		dp_tab = [math.inf for _ in range(amount + 1)]
		dp_tab[0] = 0
		for i in range(len(coins)):
			for a in range(1, amount + 1):
				if a >= coins[i]:
					dp_tab[a] = min(dp_tab[a], 1 + dp_tab[a - coins[i]])
		return dp_tab[amount]

	def do_td_mem(self, cache, coins, amount, index):
		if amount == 0:
			return 0
		if len(coins) <= index:
			return math.inf
		if cache[index][amount] == math.inf:
			count_keeping_element = math.inf
			if coins[index] <= amount:
				temp = self.do_td_mem(cache, coins, amount - coins[index], index)
				if temp != math.inf:
					count_keeping_element = temp + 1
			count_skipping_element = self.do_td_mem(cache, coins, amount, index + 1)
			cache[index][amount] = min(count_keeping_element, count_skipping_element)
		return cache[index][amount]

	def do_bf(self, coins, amount, index):
		if amount == 0:
			return 0
		n = len(coins)
		if n <= index:
			return math.inf
		count_keeping_element = math.inf
		if coins[index] <= amount:
			temp = self.do_bf(coins, amount - coins[index], index)
			if temp != math.inf:
				count_keeping_element = temp + 1
		count_skipping_element = self.do_bf(coins, amount, index + 1)
		return min(count_keeping_element, count_skipping_element)

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 1:
			return 0
		coins.sort()
		output = self.do_du_tab(coins, amount)
		return -1 if output == math.inf else output


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		records = [-2] * amount
		return helper(amount, coins, records)

def helper(amount, coins, records):
	if amount == 0:
		return 0
	if amount < 0:
		return -1
	if records[amount - 1] != -2:
		min_number = records[amount - 1]
	else:
		min_number = math.inf
		for c in coins:
			val = helper(amount - c, coins, records)
			if val != -1:
				val += 1
				min_number = min(val, min_number)
	if min_number == math.inf:
		records[amount - 1] = -1
		return -1
	else:
		records[amount - 1] = min_number
		return min_number


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [[float('inf')] * (amount + 1) for _ in range(len(coins))]
		for r in range(len(coins)):
			dp[r][0] = 0
		for r in range(len(coins)):
			for c in range(1, amount + 1):
				take = leave = float('inf')
				if c - coins[r] >= 0:
					take = dp[r][c - coins[r]] + 1
				if r > 0:
					leave = dp[r - 1][c]
				dp[r][c] = min(leave, take)
		return dp[-1][-1] if dp[-1][-1] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], a: int) -> int:
		l = len(coins)
		mem = []
		for i in range(l + 1):
			mem.append([0] * (a + 1))
			for j in range(a + 1):
				if i == 0:
					mem[i][j] = float('inf')
				if j == 0:
					mem[i][j] = 0
				if i > 0 and j > 0:
					if coins[i - 1] <= j:
						mem[i][j] = min(1 + mem[i][j - coins[i - 1]], mem[i - 1][j])
					else:
						mem[i][j] = mem[i - 1][j]
		if mem[l][a] == float('inf'):
			return -1
		return mem[l][a]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		n = len(coins)
		dp = [[0 for j in range(amount + 1)] for i in range(n)]
		for j in range(amount + 1):
			dp[0][j] = -1 if j % coins[0] else j // coins[0]
		for i in range(1, n):
			for j in range(1, amount + 1):
				includeDenom = -1 if coins[i] > j else dp[i][j - coins[i]]
				excludeDenom = dp[i - 1][j]
				if includeDenom == -1 and excludeDenom == -1:
					dp[i][j] = -1
				elif includeDenom == -1:
					dp[i][j] = excludeDenom
				elif excludeDenom == -1:
					dp[i][j] = includeDenom + 1
				else:
					dp[i][j] = min(includeDenom + 1, excludeDenom)
		return dp[n - 1][amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = [[float('inf') for _ in range(amount + 1)] for _ in range(len(coins))]
		for x in range(len(coins)):
			memo[x][0] = 0
		for (i, coin) in enumerate(coins):
			for tot in range(1, amount + 1):
				if i > 0:
					memo[i][tot] = memo[i - 1][tot]
				if coin <= tot:
					memo[i][tot] = min(memo[i][tot], memo[i][tot - coin] + 1)
		out = memo[len(coins) - 1][amount]
		return -1 if out == float('inf') else out


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = set(coins)
		dp = [float('inf') if i not in coins else 1 for i in range(amount + 1)]
		result = self.helper(coins, amount, dp)
		return -1 if result == float('inf') else result

	def helper(self, coins, amount, dp):
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if dp[amount] != float('inf'):
			return dp[amount]
		current_min = float('inf')
		for coin in coins:
			result = self.helper(coins, amount - coin, dp)
			if result != -1:
				current_min = min(current_min, 1 + result)
		if current_min == float('inf'):
			dp[amount] = -1
			return -1
		dp[amount] = current_min
		return current_min


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.amount = amount
		self.coins = coins
		n = len(coins)
		self.memo = [-1] * (self.amount + 1)
		val = self.coindp(amount)
		if val == float('inf'):
			return -1
		else:
			return val

	def coindp(self, i):
		if i < 0:
			return float('inf')
		if i == 0:
			return 0
		if self.memo[i] >= 0:
			return self.memo[i]
		mini = float('inf')
		for coin in self.coins:
			mini = min(mini, self.coindp(i - coin) + 1)
		self.memo[i] = mini
		return self.memo[i]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def dfs(start, amount, n_coins):
			coin = coins[start]
			div = amount // coin
			amount %= coin
			n_coins += div
			if amount == 0:
				self.minimum = min(n_coins, self.minimum)
				return
			if start < length:
				dfs(start + 1, amount, n_coins)
				next_coin = coins[start + 1]
				for _ in range(div):
					amount += coin
					n_coins -= 1
					if (self.minimum - n_coins - 1) * next_coin + 1 > amount:
						dfs(start + 1, amount, n_coins)
					else:
						break
		coins.sort(reverse=True)
		self.minimum = float('inf')
		length = len(coins) - 1
		dfs(0, amount, 0)
		return self.minimum if self.minimum < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort(reverse=True)
		res = amount // coins[-1] + 1

		def comb(cursum, num, index):
			nonlocal res
			if (amount - cursum) / coins[index] >= res - num:
				return
			for i in range(index, len(coins)):
				newsum = cursum + coins[i]
				if newsum == amount:
					res = min(num + 1, res)
					return
				elif newsum < amount:
					comb(newsum, num + 1, i)
		comb(0, 0, 0)
		if res == amount // coins[-1] + 1:
			return -1
		return res


class Solution:

	def coinChange(self, coin: List[int], sum1: int) -> int:
		maxv = float('inf') - 1
		n = len(coin)
		t = [[0 for j in range(sum1 + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(sum1 + 1):
				if i == 0 and j == 0:
					t[i][j] = maxv
				elif j == 0:
					t[i][j] = 0
				elif i == 0:
					t[i][j] = maxv
		for i in range(1, n + 1):
			for j in range(1, sum1 + 1):
				if coin[i - 1] <= j:
					t[i][j] = min(t[i][j - coin[i - 1]] + 1, t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[n][sum1] == float('inf'):
			return -1
		return t[n][sum1]


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins:
			return -1
		if amount == 0:
			return 0
		memo = [0] * amount

		def findNumCoins(remainingAmount: int) -> int:
			nonlocal memo
			if remainingAmount < 0:
				return -1
			if remainingAmount == 0:
				return 0
			memo_idx = remainingAmount - 1
			if memo[memo_idx] != 0:
				return memo[memo_idx]
			local_min = math.inf
			for coin in coins:
				res = findNumCoins(remainingAmount - coin)
				if res >= 0:
					local_min = min(local_min, 1 + res)
			num_coins = -1 if local_min == math.inf else local_min
			memo[memo_idx] = num_coins
			return num_coins
		return findNumCoins(amount)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [0] * (amount + 1)
		for i in range(1, amount + 1):
			minn = float('inf')
			for j in coins:
				if i == j:
					minn = min(minn, 1)
					continue
				if i - j > 0:
					minn = min(minn, 1 + dp[i - j])
			dp[i] = minn
		return dp[amount] if dp[amount] != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		self.count = [float('inf')] * (amount + 1)
		self.count[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				rest = i - coin
				if rest >= 0 and self.count[rest] != float('inf'):
					self.count[i] = min(1 + self.count[rest], self.count[i])
		if self.count[-1] == float('inf'):
			return -1
		else:
			return self.count[-1]


from functools import lru_cache

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dict_ = set(coins)
		count = [0] * amount

		def top_down(rem):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if count[rem - 1] != 0:
				return count[rem - 1]
			min_ = float('inf')
			for coin in dict_:
				res = top_down(rem - coin)
				if res >= 0:
					min_ = min(1 + res, min_)
			count[rem - 1] = -1 if min_ == float('inf') else min_
			return count[rem - 1]

		def bottom_up():
			dpa = [float('inf')] * (amount + 1)
			dpa[0] = 0
			for i in range(1, len(dpa)):
				for coin in dict_:
					if i >= coin:
						remainder = i - coin
						dpa[i] = min(dpa[remainder] + 1, dpa[i])
			return dpa[amount] if dpa[amount] != float('inf') else -1
		return bottom_up()


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		coins.sort()
		self.coins = coins
		self.memo = {}
		self.recursion(amount)
		return -1 if self.memo[amount] == float('inf') else self.memo[amount]

	def recursion(self, amt):
		min_coins = float('inf')
		if amt == 0:
			return 0
		if amt in self.memo:
			return self.memo[amt]
		for coin in self.coins:
			if coin > amt:
				break
			x = self.recursion(amt - coin)
			min_coins = min(min_coins, x)
		self.memo[amt] = 1 + min_coins
		return self.memo[amt]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		N = len(coins)
		mem = [[None for i in range(amount + 1)] for j in range(N + 1)]

		def helper(target, i):
			if mem[i][target] != None:
				return mem[i][target]
			if target == 0:
				return 0
			if i == N and target > 0:
				return float('inf')
			if coins[i] > target:
				mem[i][target] = helper(target, i + 1)
			else:
				include = 1 + helper(target - coins[i], i)
				exclude = helper(target, i + 1)
				mem[i][target] = min(include, exclude)
			return mem[i][target]
		ans = helper(amount, 0)
		return ans if ans != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		count = collections.defaultdict(int)

		def coinChangeHelper(coins, rem, count):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if count[rem] != 0:
				return count[rem]
			minCount = 2 ** 32
			for coin in coins:
				makeChange = coinChangeHelper(coins, rem - coin, count)
				if makeChange > -1 and makeChange < minCount:
					minCount = makeChange + 1
			count[rem] = -1 if minCount == 2 ** 32 else minCount
			return count[rem]
		return coinChangeHelper(coins, amount, count)


class Solution:

	def coinChange(self, coins, amount):
		coins.sort()
		stack = [(0, 0, len(coins))]
		min_steps = 2 ** 31
		while len(stack) != 0:
			(steps, accumulated, sequence) = stack.pop()
			if accumulated == amount:
				min_steps = min(min_steps, steps)
			if accumulated > amount or amount - accumulated > coins[sequence - 1] * (min_steps - steps):
				continue
			for (seq, coin) in enumerate(coins[:sequence]):
				stack.append((steps + 1, accumulated + coin, seq + 1))
		return min_steps if min_steps != 2 ** 31 else -1


class Solution:

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


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [[math.inf for _ in range(amount + 1)] for _ in coins]
		for i in range(len(coins)):
			dp[i][0] = 0
		for i in range(1, amount + 1):
			if coins[0] <= i:
				dp[0][i] = 1 + dp[0][i - coins[0]]
		for i in range(1, len(coins)):
			for j in range(1, amount + 1):
				(take, leave) = (math.inf, math.inf)
				if coins[i] <= j:
					take = 1 + dp[i][j - coins[i]]
				leave = dp[i - 1][j]
				dp[i][j] = min(take, leave)
		return dp[-1][-1] if dp[-1][-1] != math.inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if len(coins) == 0:
			return 0
		coins = sorted(coins, reverse=True)
		memo = {}

		def coinChangeRec(index, amount):
			if amount == 0:
				return 0
			if amount < 0 or index == len(coins):
				return math.inf
			if (index, amount) in memo:
				return memo[index, amount]
			withCoin = coinChangeRec(index, amount - coins[index]) + 1
			withoutCoin = coinChangeRec(index + 1, amount)
			memo[index, amount] = min(withCoin, withoutCoin)
			return min(withCoin, withoutCoin)
		minCoins = coinChangeRec(0, amount)
		if minCoins == math.inf:
			return -1
		return minCoins


class Solution:

	def aux(self, coins, amount, cache):
		if amount in cache:
			return cache[amount]
		res = -1
		for i in range(len(coins)):
			if coins[i] < amount:
				right = cache[amount - coins[i]] if amount - coins[i] in cache else self.aux(coins, amount - coins[i], cache)
				if right != -1 and res == -1:
					res = 1 + right
				elif right != -1 and res != -1:
					res = min(res, 1 + right)
		cache[amount] = res
		return cache[amount]

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		cache = dict(list(zip(coins, [1] * len(coins))))
		return self.aux(coins, amount, cache)


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dic = {0: 0}

		def change(amount):
			if amount < 0:
				return -1
			if amount in dic:
				return dic[amount]
			res = [change(amount - i) for i in coins if change(amount - i) >= 0]
			if not res:
				dic[amount] = -1
			else:
				dic[amount] = min(res) + 1
			return dic[amount]
		return change(amount)


class Solution:

	def __init__(self):
		self.table = {}

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if amount in self.table:
			return self.table[amount]
		possible_answers = [self.coinChange(coins, amount - coin) + 1 for coin in coins]
		possible_answers = [ans for ans in possible_answers if ans >= 1]
		if possible_answers:
			ans = min(possible_answers)
		else:
			ans = -1
		self.table[amount] = ans
		return ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		sz = len(coins) + 1
		dp = [[sys.maxsize] * sz for _ in range(amount + 1)]
		for i in range(sz):
			dp[0][i] = 0
		for a in range(1, amount + 1):
			for i in range(1, sz):
				dp[a][i] = dp[a][i - 1]
				if a - coins[i - 1] >= 0:
					dp[a][i] = min(1 + dp[a - coins[i - 1]][i], dp[a][i])
		return -1 if dp[amount][sz - 1] == sys.maxsize else dp[amount][sz - 1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = [amount] * (amount + 1)
		dp[0] = 0
		pos = 1
		contain = False
		while pos < len(dp):
			for coin in coins:
				if coin == 1:
					contain = True
				if pos - coin >= 0:
					dp[pos] = min(dp[pos], dp[pos - coin] + 1)
			pos += 1
		print(dp)
		if dp[-1] == amount and (not contain):
			return -1
		return dp[-1]


class Solution:

	def coinChange(self, coins: List[int], a: int) -> int:
		if a == 0:
			return 0
		dp = [-1 for i in range(a + 1)]
		dp[0] = 1
		coins.sort()
		for i in range(1, len(coins) + 1):
			for j in range(1, a + 1):
				if coins[i - 1] == j:
					dp[j] = 1
				else:
					c = -1
					if j - coins[i - 1] > 0 and dp[j - coins[i - 1]] != -1:
						c = dp[j - coins[i - 1]] + 1
					d = dp[j]
					if c != -1 and d != -1:
						dp[j] = min(c, d)
					elif c == -1 and d != -1:
						dp[j] = d
					elif c != -1:
						dp[j] = c
		if dp[a] == -1:
			return -1
		else:
			return dp[a]


class Solution:

	def coinChange(self, coins, amount):
		if amount < 1:
			return 0

		def count_change(coins, amount, dic={}):
			if amount < 0:
				return -1
			if amount == 0:
				return 0
			if amount in dic:
				return dic[amount]
			minimum = float('inf')
			for i in range(len(coins)):
				current = count_change(coins, amount - coins[i], dic)
				if current >= 0 and current < minimum:
					minimum = 1 + current
			if minimum == float('inf'):
				dic[amount] = -1
			else:
				dic[amount] = minimum
			return dic[amount]
		return count_change(coins, amount, {})


class Solution:

	def __init__(self):
		self.count = []

	def coinChange(self, coins: List[int], amount: int) -> int:
		if len(self.count) < amount:
			self.count = [-1] * (amount + 1)
			self.skip = [False] * (amount + 1)
		if amount is 0:
			return 0
		elif amount < 0:
			return -1
		else:
			if self.count[amount] < 0 and (not self.skip[amount]):
				tmp = float('inf')
				for co in coins:
					previous = self.coinChange(coins, amount - co)
					if previous >= 0:
						self.count[amount] = min(previous + 1, tmp)
						tmp = self.count[amount]
					else:
						continue
				self.skip[amount] = True
			return self.count[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		cache = {}

		def subproblem(i, t):
			if t == 0:
				return 0
			if (i, t) in cache:
				return cache[i, t]
			val = coins[i]
			if val > t:
				choice_take = math.inf
			elif val == t:
				choice_take = 1
			else:
				choice_take = 1 + subproblem(i, t - val)
			if i == 0:
				choice_leave = math.inf
			else:
				choice_leave = subproblem(i - 1, t)
			optimal = min(choice_take, choice_leave)
			cache[i, t] = optimal
			return optimal
		mincoins = subproblem(len(coins) - 1, amount)
		if mincoins == math.inf:
			return -1
		else:
			return mincoins


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		t = [[0 for x in range(amount + 1)] for x in range(len(coins) + 1)]
		for j in range(amount + 1):
			t[0][j] = 1000
		for i in range(1, len(coins) + 1):
			t[i][0] = 0
		for i in range(1, len(coins) + 1):
			for j in range(1, amount + 1):
				if j % coins[i - 1] == 0:
					t[i][j] = j / coins[i - 1]
				else:
					t[i][j] = 1000
		for i in range(1, len(coins) + 1):
			for j in range(1, amount + 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[len(coins)][amount] != 1000:
			return t[len(coins)][amount]
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.res = float('inf')
		n = len(coins)
		coins.sort(reverse=True)

		def helper(cur, start, cnt, n):
			if cur == amount:
				self.res = min(self.res, cnt)
			if cur > amount:
				return
			for i in range(start, n):
				if cur + coins[i] <= amount and cur + coins[i] * (self.res - cnt) > amount:
					helper(cur + coins[i], i, cnt + 1, n)
		helper(0, 0, 0, n)
		return self.res if self.res < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		n = len(coins)
		d = [[-1] * (amount + 1) for i in range(n + 1)]
		for i in range(amount + 1):
			if i % coins[0] == 0:
				d[1][i] = i // coins[0]
		for i in range(n + 1):
			d[i][0] = 0
		for i in range(2, n + 1):
			for j in range(1, amount + 1):
				if j - coins[i - 1] >= 0:
					if d[i - 1][j] != -1 and d[i][j - coins[i - 1]] != -1:
						d[i][j] = min(d[i - 1][j], d[i][j - coins[i - 1]] + 1)
					elif d[i - 1][j] == -1 and d[i][j - coins[i - 1]] != -1:
						d[i][j] = d[i][j - coins[i - 1]] + 1
					elif d[i - 1][j] != -1 and d[i][j - coins[i - 1]] == -1:
						d[i][j] = d[i - 1][j]
					else:
						d[i][j] = d[i - 1][j]
				else:
					d[i][j] = d[i - 1][j]
		return d[n][amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		n_coins = len(coins)
		least_coin = coins[0]
		max_amount = amount + 1
		mat = [[0 for i in range(amount + 1)] for i in range(n_coins + 1)]
		if amount == 0:
			return 0
		if amount < least_coin:
			return -1
		for i in range(amount + 1):
			if i % least_coin == 0:
				mat[1][i] = i // least_coin
			else:
				mat[1][i] = -1
		for i in range(2, n_coins + 1):
			for j in range(1, amount + 1):
				curr_coin = coins[i - 1]
				if j - curr_coin >= 0:
					if mat[i][j - curr_coin] == -1:
						mat[i][j] = mat[i - 1][j]
					elif mat[i - 1][j] == -1:
						mat[i][j] = 1 + mat[i][j - curr_coin]
					elif mat[i][j - curr_coin] == -1 and mat[i - 1][j] == -1:
						mat[i][j] = -1
					else:
						mat[i][j] = min(1 + mat[i][j - curr_coin], mat[i - 1][j])
				else:
					mat[i][j] = mat[i - 1][j]
		return mat[-1][-1]


class Solution:

	def back_tracking_solution(self):

		def _is_solution(amount_left):
			if amount_left == 0:
				return True
			return False

		def _process_solution(num_coins_used, fewest_coins):
			if num_coins_used < fewest_coins[0]:
				fewest_coins[0] = num_coins_used

		def _candidate_coins_start_idx(amount_left, coins, current_coin_start_idx):
			for i in range(current_coin_start_idx, len(coins)):
				if amount_left >= coins[i]:
					return i
			return None

		def _backtrack(amount_left, num_coins_used, current_fewest_coins, coins, current_coin_start_idx):
			if _is_solution(amount_left):
				_process_solution(num_coins_used, current_fewest_coins)
			else:
				real_coin_start_idx = _candidate_coins_start_idx(amount_left, coins, current_coin_start_idx)
				if real_coin_start_idx is not None:
					for i in range(real_coin_start_idx, len(coins)):
						_backtrack(amount_left - coins[i], num_coins_used + 1, current_fewest_coins, coins, i)
		return _backtrack

	def dynamic_programming_solution(self):

		def _dp_bad(amount, coins):
			sorted_coins = sorted(coins)
			cache = [[float('inf')] * len(coins) for i in range(amount + 1)]
			for denom_idx in range(len(sorted_coins)):
				cache[0][denom_idx] = 0
			for amt in range(amount + 1):
				cache[amt][0] = amt // sorted_coins[0] if amt % sorted_coins[0] == 0 else float('inf')
			for i in range(1, len(cache)):
				for j in range(1, len(sorted_coins)):
					max_num_of_denom = i // sorted_coins[j] + 1
					for k in range(max_num_of_denom):
						cache[i][j] = min(cache[i][j], k + cache[i - k * sorted_coins[j]][j - 1])
			return cache[amount][-1]

		def _dp_cache_recursive(amount, coins, cache):
			if amount in cache:
				return cache[amount]
			for c in coins:
				if amount >= c:
					intermediate = 1 + _dp_cache_recursive(amount - c, coins, cache)
					if amount in cache:
						cache[amount] = min(cache[amount], intermediate)
					else:
						cache[amount] = intermediate
			return cache[amount] if amount in cache else float('inf')

		def _dp_bottom_up_1(amount, coins):
			sorted_coins = sorted(coins)
			cache = [[float('inf')] * len(coins) for i in range(amount + 1)]
			for denom_idx in range(len(sorted_coins)):
				cache[0][denom_idx] = 0
			for amt in range(1, len(cache)):
				for denom_idx in range(len(sorted_coins)):
					amt_left = amt - sorted_coins[denom_idx]
					if amt_left >= 0:
						cache[amt][denom_idx] = 1 + min(cache[amt_left][0:denom_idx + 1])
			return min(cache[amount])
		return _dp_bottom_up_1

	def coinChange(self, coins: List[int], amount: int) -> int:
		result = self.dynamic_programming_solution()(amount, coins)
		return -1 if result == float('inf') else result


import queue

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		q = queue.Queue()
		q.put(amount)
		q.put(None)
		level = 0
		visited = {amount}
		while not q.empty():
			num = q.get()
			if num is None:
				if q.empty():
					break
				q.put(None)
				level += 1
				continue
			for coin in coins:
				if num - coin > 0 and num - coin not in visited:
					q.put(num - coin)
					visited.add(num - coin)
				elif num - coin == 0:
					return level + 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		m = Counter(coins)

		def recurse(left, count) -> int:
			if left in m:
				return m[left]
			if left == 0:
				m[left] = count
				return count
			smallest = math.inf
			for c in coins:
				if left - c >= 0:
					smallest = min(smallest, recurse(left - c, count + 1))
			m[left] = smallest + 1
			return smallest + 1
		recurse(amount, 0)
		if m[amount] == math.inf:
			return -1
		return m[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		table = [float('inf') for _ in range(amount + 1)]
		i = 0
		table[0] = 0
		for coin in coins:
			if coin <= amount:
				table[coin] = 1
		while i <= amount:
			for coin in coins:
				if i - coin >= 0:
					table[i] = min(table[i - coin] + 1, table[i])
			i += 1
		return table[amount] if table[amount] != float('inf') else -1


import math

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.c = set([x for x in coins if x <= amount])
		self.coins = list(self.c)
		self.dic = {}
		if amount == 0:
			return 0
		if amount in self.c:
			return 1
		res = math.inf
		for i in range(len(self.coins)):
			ci = self.dp(amount - self.coins[i])
			if ci > 0:
				res = min(res, ci + 1)
		return res if res != math.inf else -1

	def dp(self, amount):
		if amount in self.c:
			return 1
		if amount in self.dic:
			return self.dic[amount]
		list2 = [x for x in self.coins if x <= amount]
		if len(list2) == 0:
			return -1
		res = math.inf
		for i in range(len(list2)):
			ci = self.dp(amount - list2[i])
			if ci > 0:
				res = min(res, ci + 1)
		self.dic[amount] = res
		return res


class Solution:

	def helper(self, coins, amount, cache, current=[]):
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		else:
			if amount in cache:
				return cache[amount]
			currMin = sys.maxsize
			for coin in coins:
				current.append(coin)
				currNum = self.helper(coins, amount - coin, cache, current)
				if currNum != -1:
					if currNum < currMin:
						currMin = currNum + 1
				current.pop()
			cache[amount] = currMin
			return currMin

	def coinChange(self, coins, amount):
		cache = {}
		val = self.helper(coins, amount, cache)
		memo = [sys.maxsize] * (amount + 1)
		memo[0] = 0
		for i in range(1, amount + 1):
			for coin in coins:
				newIndex = i - coin
				if newIndex >= 0:
					if memo[newIndex] + 1 < memo[i]:
						memo[i] = memo[newIndex] + 1
		if memo[amount] == sys.maxsize:
			return -1
		else:
			return memo[amount]


class Solution:

	def coinChange(self, coins: [int], amount: int) -> int:
		self.ans = float('inf')
		self.dict = {}
		coins.sort(reverse=True)

		def helper(num, depth):
			if num == 0:
				self.ans = min(self.ans, depth)
				return
			for c in coins:
				res = num - c
				if res >= 0:
					if res in self.dict:
						if self.dict[res] > depth + 1 and depth + 1 < self.ans:
							self.dict[res] = depth + 1
							helper(res, depth + 1)
					else:
						self.dict[res] = depth + 1
						helper(res, depth + 1)
		helper(amount, 0)
		return self.ans if self.ans < float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(None)
		def recurse(amount, pos):
			if pos == len(coins):
				return 10000
			if amount == 0:
				return 0
			if coins[pos] <= amount:
				return min(recurse(amount - coins[pos], pos) + 1, recurse(amount, pos + 1))
			else:
				return recurse(amount, pos + 1)
		count = recurse(amount, 0)
		if count >= 10000:
			return -1
		return count


class Solution:

	def recursion(self, coins, remain, dic):
		if remain < 0:
			return float('inf')
		if remain == 0:
			return 0
		if remain in dic.keys():
			return dic[remain]
		min_coin = float('inf')
		for coin in coins:
			number_coin = None
			prev_num = self.recursion(coins, remain - coin, dic)
			if prev_num == float('inf'):
				number_coin = prev_num
			else:
				number_coin = prev_num + 1
			min_coin = min(min_coin, number_coin)
		dic[remain] = min_coin
		return min_coin

	def coinChange(self, coins: List[int], amount: int) -> int:
		remain = amount
		count = 0
		dic = {}
		number = self.recursion(coins, remain, dic)
		if number == float('inf'):
			return -1
		else:
			return number


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = {}

		def dfs(total):
			if total < 0:
				return float('inf')
			if total == 0:
				return 0
			if total in list(dp.keys()):
				return dp[total]
			for c in coins:
				x = total - c
				if total not in list(dp.keys()):
					dp[total] = dfs(x) + 1
				else:
					dp[total] = min(dp[total], dfs(x) + 1)
			return dp[total]
		ans = dfs(amount)
		if ans < float('inf'):
			return ans
		else:
			return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		coins.sort()
		table = [[-1 for i in range(amount + 1)] for i in range(len(coins))]
		for i in range(len(coins)):
			for j in range(amount + 1):
				if coins[i] > j and i > 0 and (table[i - 1][j] > 0):
					table[i][j] = table[i - 1][j]
				elif j >= coins[i]:
					x = j - coins[i]
					pre_val = 9999999
					calculated_val = 0
					if i > 0 and table[i - 1][j] > 0:
						pre_val = table[i - 1][j]
					if x > 0:
						if table[i][x] > 0:
							calculated_val = table[i][x]
							table[i][j] = min(1 + calculated_val, pre_val)
						elif i > 0 and pre_val != 9999999:
							table[i][j] = pre_val
					elif x == 0:
						table[i][j] = min(1 + calculated_val, pre_val)
		return table[len(coins) - 1][amount]


class Solution:

	def coinChange(self, coins: List[int], total: int) -> int:
		dic = {0: 0}

		def helper(amount):
			if amount in coins:
				dic[amount] = 1
			elif amount < 0:
				return float('inf')
			elif amount not in dic:
				dic[amount] = min([helper(amount - c) + 1 for c in coins])
			return dic[amount]
		return helper(total) if helper(total) != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not coins:
			return -1
		n = len(coins)
		if amount == 0:
			return 0
		fewest = [[0] * n for k in range(amount + 1)]
		for k in range(n):
			fewest[0][k] = 0
		for p in range(1, amount + 1):
			is_divisible = p % coins[0] == 0
			if is_divisible:
				fewest[p][0] = p // coins[0]
			else:
				fewest[p][0] = -1
		for k in range(1, n):
			for p in range(1, amount + 1):
				if p < coins[k]:
					fewest[p][k] = fewest[p][k - 1]
				elif fewest[p - coins[k]][k] == -1:
					fewest[p][k] = fewest[p][k - 1]
				elif fewest[p][k - 1] == -1:
					fewest[p][k] = fewest[p - coins[k]][k] + 1
				else:
					fewest[p][k] = min(fewest[p - coins[k]][k] + 1, fewest[p][k - 1])
		return fewest[p][n - 1]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		coins.reverse()
		lookup = {}

		def find_combos(total_remain, total_coins):
			if total_remain in lookup:
				if lookup[total_remain] > total_coins:
					lookup[total_remain] = total_coins
				else:
					return
			else:
				lookup[total_remain] = total_coins
			for coin in coins:
				if total_remain - coin < 0:
					continue
				find_combos(total_remain - coin, total_coins + 1)
		find_combos(amount, 0)
		if 0 in lookup:
			return lookup[0]
		else:
			return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		dp = {i: [] for i in range(1, amount + 1)}
		coins.sort()
		for intermediate_amount in range(1, amount + 1):
			for denom in reversed(coins):
				if intermediate_amount == denom:
					dp[intermediate_amount] = [denom]
					break
				elif denom < intermediate_amount and dp[intermediate_amount - denom] != []:
					if dp[intermediate_amount] == [] or len(dp[intermediate_amount]) > len(dp[intermediate_amount - denom]) + 1:
						dp[intermediate_amount] = dp[intermediate_amount - denom] + [denom]
		return len(dp[amount]) if len(dp[amount]) > 0 else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [[float('INF') for i in range(amount + 1)] for j in range(len(coins) + 1)]
		for i in range(len(coins) + 1):
			dp[i][0] = 0
		for i in range(1, len(coins) + 1):
			for j in range(1, amount + 1):
				if j - coins[i - 1] < 0:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
		if dp[len(coins)][amount] == float('INF'):
			return -1
		else:
			return dp[len(coins)][amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		def coinchangehelper(rem):
			if rem < 0:
				return -1
			if rem == 0:
				return 0
			if rem in memo:
				return memo[rem]
			count = float('inf')
			for coin in coins:
				sub = coinchangehelper(rem - coin)
				if sub >= 0:
					count = min(count, 1 + sub)
			memo[rem] = count
			return memo[rem]
		memo = {}
		res = coinchangehelper(amount)
		return res if res != float('inf') else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = [float('inf') for _ in range(amount + 1)]
		if amount == 0:
			return 0
		for i in range(0, len(dp)):
			for c in coins:
				if i >= c:
					if i % c == 0:
						dp[i] = min(int(i / c), dp[i])
					elif i - c >= 0 and dp[i - c] != float('inf'):
						dp[i] = min(int(1 + dp[i - c]), dp[i])
		ret_val = dp[amount]
		if ret_val == float('inf'):
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		self.dp = [float('inf')] * (amount + 1)
		self.dp[0] = 0

		def change(a):
			if a < 0:
				return -1
			if a == 0:
				return 0
			if self.dp[a] != float('inf'):
				return self.dp[a]
			for c in coins:
				tmp = change(a - c)
				if tmp != -1:
					self.dp[a] = min(tmp + 1, self.dp[a])
			if self.dp[a] == float('inf'):
				self.dp[a] = -1
			return self.dp[a]
		change(amount)
		return self.dp[amount] if self.dp[amount] != float('inf') else -1


class Solution:

	def coinChange_bottomUp(self, coins: List[int], amount: int) -> int:
		lookup = {x: amount + 1 for x in range(1, amount + 1)}
		lookup[0] = 0
		for i in range(amount + 1):
			for coin in coins:
				remainder = i - coin
				if remainder < 0:
					continue
				best_min = min(lookup[remainder] + 1, lookup[i])
				lookup[i] = best_min
		if lookup[i] > amount:
			return -1
		else:
			return lookup[i]

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		coins.reverse()
		lookup = {}

		def find_combos(total_remain, total_coins):
			if total_remain in lookup:
				if lookup[total_remain] > total_coins:
					lookup[total_remain] = total_coins
				else:
					return
			else:
				lookup[total_remain] = total_coins
			for coin in coins:
				if total_remain - coin < 0:
					continue
				find_combos(total_remain - coin, total_coins + 1)
		find_combos(amount, 0)
		return lookup[0] if 0 in lookup else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		level = seen = {0}
		number = 0
		while level:
			if amount in seen:
				return number
			level = {pre_amount + coin for pre_amount in level for coin in coins if pre_amount + coin <= amount}
			seen.update(level)
			number += 1
		return -1


from functools import lru_cache
from math import inf

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:

		@lru_cache(maxsize=None)
		def cc(i, amount):
			if amount == 0:
				return 0
			elif i < 0 or amount < 0:
				return inf
			else:
				(incl, excl) = (cc(i - 1, amount), cc(i, amount - coins[i]) + 1)
				return min(max(incl, 0), max(excl, 0))
		result = cc(len(coins) - 1, amount)
		return result if result < inf else -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		memo = [[-1 for _ in range(amount + 1)] for _ in coins]
		for i in range(len(coins) - 1, -1, -1):
			for j in range(amount + 1):
				if j == 0:
					memo[i][j] = 0
					continue
				if j - coins[i] >= 0 and memo[i][j - coins[i]] != -1 and (i + 1 < len(coins)) and (memo[i + 1][j] != -1):
					memo[i][j] = min(memo[i][j - coins[i]] + 1, memo[i + 1][j])
				elif j - coins[i] >= 0 and memo[i][j - coins[i]] != -1:
					memo[i][j] = memo[i][j - coins[i]] + 1
				elif i + 1 < len(coins) and memo[i + 1][j] != -1:
					memo[i][j] = memo[i + 1][j]
		return memo[0][amount]


class Solution:

	def __init__(self):
		self.total_min = 0
		self.change_map = {0: 0}

	def changer(self, coins_obj, amount_obj):
		if amount_obj == 0:
			self.change_map[amount_obj] = 0
			return 0
		if min(coins_obj) > amount_obj:
			self.change_map[amount_obj] = -1
			return -1
		rev_coins_obj = list(reversed(coins_obj))
		for el in rev_coins_obj:
			if el <= amount_obj:
				if amount_obj - el in self.change_map.keys():
					tmp = self.change_map[amount_obj - el]
				else:
					tmp = Solution.changer(self, coins_obj, amount_obj - el)
				if tmp != -1:
					key = tmp + 1
					if amount_obj not in self.change_map.keys():
						self.change_map[amount_obj] = key
					elif amount_obj in self.change_map.keys():
						if key < self.change_map[amount_obj]:
							self.change_map[amount_obj] = key
		if amount_obj not in self.change_map.keys():
			self.change_map[amount_obj] = -1
			return -1
		elif amount_obj in self.change_map.keys():
			return self.change_map[amount_obj]

	def coinChange(self, coins: List[int], amount: int) -> int:
		Solution.changer(self, coins, amount)
		if amount not in self.change_map.keys():
			return -1
		return self.change_map[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		start = [0]
		visited = [False] * (amount + 1)
		visited[0] = True
		numCoins = 1
		nextStart = []
		while start:
			for v in start:
				for coin in coins:
					nextVal = v + coin
					if nextVal > amount or visited[nextVal]:
						continue
					elif nextVal == amount:
						return numCoins
					else:
						visited[nextVal] = True
						nextStart.append(nextVal)
			(start, nextStart) = (nextStart, [])
			numCoins += 1
		return -1


from queue import Queue

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		q = Queue()
		mem = dict()
		q.put((0, 0))
		while not q.empty():
			curr = q.get()
			for c in coins:
				tot = curr[1] + c
				if tot > amount:
					continue
				if tot == amount:
					return curr[0] + 1
				if tot in mem and mem[tot] <= curr[0] + 1:
					continue
				q.put((curr[0] + 1, tot))
				mem[tot] = curr[0] + 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		mem = {}

		def helper(amt):
			if amt < 0:
				return -1
			elif amt == 0:
				return 0
			elif amt in mem:
				return mem[amt]
			min_coins = float('inf')
			for coin in coins:
				result = helper(amt - coin)
				if result != -1:
					min_coins = min(min_coins, 1 + result)
			mem[amt] = min_coins
			return min_coins
		output = helper(amount)
		return -1 if output == float('inf') else output


class Solution:

	def changeCoin(self, coins, amount, change):
		if amount < 0:
			return -1
		if amount == 0:
			return 0
		if amount in change:
			return change[amount]
		costs = []
		for coin in coins:
			cost = self.changeCoin(coins, amount - coin, change)
			if amount - coin in change:
				change[amount - coin] = min(cost, change[amount - coin])
			else:
				change[amount - coin] = cost
			if cost != -1:
				costs.append(cost)
		if len(costs) == 0:
			return -1
		return 1 + min(costs)

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort()
		coins = [coin for coin in coins if coin <= amount]
		change = {}
		return self.changeCoin(coins, amount, change)


import numpy as np

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		maximum = amount + 1
		dp = np.full(maximum, maximum)
		dp[0] = 0
		for i in range(1, maximum):
			for j in coins:
				if j <= i:
					dp[i] = min(dp[i], dp[i - j] + 1)
		if dp[amount] > amount:
			return -1
		return dp[amount]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		rows = amount + 1
		cols = len(coins) + 1
		cache = [[0 for _ in range(cols)] for _ in range(rows)]
		for row in range(1, rows):
			cache[row][0] = -1
		for row in range(1, rows):
			for col in range(1, cols):
				newAmt = row - coins[col - 1]
				takeValue = cache[newAmt][col] if newAmt >= 0 and newAmt < len(cache) else -1
				takeCoin = 1 + takeValue if takeValue >= 0 else -1
				skipCoin = cache[row][col - 1]
				if skipCoin < 0:
					cache[row][col] = takeCoin
				elif takeCoin < 0:
					cache[row][col] = skipCoin
				else:
					cache[row][col] = min(skipCoin, takeCoin)
		return cache[amount][len(coins)]


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		self.dp = [[-1] * (amount + 1) for _ in range(len(coins) + 1)]
		value = self.solve(coins, len(coins), amount)
		return self.dp[-1][-1] if value != float('inf') else -1

	def solve(self, coins, n, amount):
		if amount == 0:
			self.dp[n][amount] = 0
			return 0
		if n == 0:
			self.dp[n][amount] = float('inf')
			return self.dp[n][amount]
		if self.dp[n][amount] != -1:
			return self.dp[n][amount]
		if coins[n - 1] <= amount:
			self.dp[n][amount] = min(1 + self.solve(coins, n, amount - coins[n - 1]), self.solve(coins, n - 1, amount))
			return self.dp[n][amount]
		else:
			self.dp[n][amount] = self.solve(coins, n - 1, amount)
			return self.dp[n][amount]


import numpy as np

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		dp = np.empty(amount + 1)
		dp.fill(math.inf)
		dp[0] = 0
		coins = sorted(coins)
		for i in range(1, amount + 1):
			for c in coins:
				if c <= i:
					dp[i] = min(dp[i], 1 + dp[i - c])
				else:
					break
		return -1 if dp[-1] == math.inf else int(dp[-1])


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		INVALID = 10 ** 10
		self.ans = INVALID

		def dfs(s, amount, count):
			if amount == 0:
				self.ans = count
				return
			if s == len(coins):
				return
			coin = coins[s]
			for i in range(amount // coin, -1, -1):
				print(i)
				print(coin)
				print(amount)
				if count + i >= self.ans:
					break
				dfs(s + 1, amount - i * coin, count + i)
		dfs(0, amount, 0)
		if self.ans == INVALID:
			return -1
		else:
			return self.ans


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins = sorted(coins)
		dp = {}

		def in_dict(val):
			return val in dp.keys() and dp[val]
		if not amount:
			return 0
		if coins[0] > amount:
			return -1
		for coin in coins:
			dp[coin] = 1
		for i in range(coins[0], min(amount, coins[-1]) + 1):
			if i in dp.keys():
				continue
			available_coins = [coin for coin in coins if coin <= i]
			possible_min_coins = [1 + dp[i - coin] for coin in available_coins if in_dict(i - coin)]
			dp[i] = min(possible_min_coins) if possible_min_coins else 0
		for i in range(coins[-1] + 1, amount + 1):
			possible_min_coins = [1 + dp[i - coin] for coin in coins if in_dict(i - coin)]
			dp[i] = min(possible_min_coins) if possible_min_coins else 0
		return dp[amount] or -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		value1 = [0]
		value2 = []
		nc = 0
		visited = [False] * (amount + 1)
		visited[0] = True
		while value1:
			nc += 1
			for v in value1:
				for coin in coins:
					newval = v + coin
					if newval <= amount:
						if not visited[newval]:
							if newval == amount:
								return nc
							visited[newval] = True
							value2.append(newval)
			(value1, value2) = (value2, [])
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		(res, seen, curr) = (0, set(), {c for c in coins if c <= amount})
		while curr:
			res += 1
			if amount in curr:
				return res
			seen |= curr
			tmp = {n + c for n in curr for c in coins}
			curr = {t for t in tmp if t not in seen and t <= amount}
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		seen = set()
		seen.add(0)
		queue = deque([0])
		count = 0
		while queue:
			if amount in queue:
				return count
			currlen = len(queue)
			for i in range(currlen):
				node = queue.popleft()
				for c in coins:
					if c + node not in seen and c + node <= amount:
						queue.append(c + node)
						seen.add(c + node)
			count += 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		q = deque([amount])
		hs = [False] * amount
		count = 0
		while q:
			l = len(q)
			while l:
				n = q.popleft()
				for c in coins:
					x = n - c
					if not x:
						return count + 1
					if x > 0 and (not hs[x]):
						hs[x] = True
						q.append(x)
				l -= 1
			count += 1
		return -1


import collections

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if not amount:
			return 0
		queue = collections.deque(coins)
		visited = set()
		count = 1
		while queue:
			for _ in range(len(queue)):
				curr = queue.popleft()
				if curr == amount:
					return count
				for next in coins:
					next += curr
					if next not in visited and next <= amount:
						visited.add(next)
						queue.append(next)
			count += 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		from collections import deque
		q = deque()
		visited = set()
		q.append(amount)
		visited.add(amount)
		steps = 0
		while q:
			for _ in range(len(q)):
				poped = q.popleft()
				if poped == 0:
					return steps
				for coin in coins:
					new = poped - coin
					if new not in visited and new >= 0:
						q.append(new)
						visited.add(new)
			steps += 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		queue = [[0, 0]]
		visited = {0}
		step = 0
		for (node, step) in queue:
			for coin in coins:
				if node + coin in visited:
					continue
				if node + coin == amount:
					return step + 1
				if node + coin < amount:
					queue.append([node + coin, step + 1])
					visited.add(node + coin)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		q = [0]
		visited = set()
		depth = 0
		while q:
			depth += 1
			level = []
			for curr in q:
				for coin in coins:
					newvalue = curr + coin
					if newvalue == amount:
						return depth
					if newvalue not in visited and newvalue < amount:
						visited.add(newvalue)
						level.append(newvalue)
			q = level
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		que = deque()
		seen = set()
		res = -1
		for coin in coins:
			if coin <= amount:
				que.append(coin)
				seen.add(coin)
		count = 1
		while que:
			prev = len(que)
			while prev > 0:
				cur = que.popleft()
				if cur == amount:
					return count
				for coin in coins:
					newamount = cur + coin
					if newamount not in seen and newamount <= amount:
						que.append(newamount)
						seen.add(newamount)
				prev -= 1
			count += 1
		return res


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		seen = level = {0}
		coin_n = 0
		while level:
			if amount in level:
				return coin_n
			level = {val + coin for val in level for coin in coins if val + coin <= amount} - seen
			seen |= level
			coin_n += 1
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		coins.sort(reverse=True)
		count = 0
		self.maxcount = float('inf')
		self.dfs(coins, count, amount)
		return -1 if self.maxcount == float('inf') else self.maxcount

	def dfs(self, coins, count, amount):
		if amount == 0:
			self.maxcount = min(self.maxcount, count)
		for i in range(len(coins)):
			if amount >= coins[i] and count + math.ceil(amount / coins[i]) < self.maxcount:
				self.dfs(coins[i:], count + 1, amount - coins[i])


from collections import deque

class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		queue = deque([[0, 0]])
		visited = {0}
		step = 0
		while queue:
			(node, step) = queue.popleft()
			for coin in coins:
				if node + coin in visited:
					continue
				if node + coin == amount:
					return step + 1
				elif node + coin < amount:
					queue.append([node + coin, step + 1])
					visited.add(node + coin)
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount < 0 or not coins:
			return -1
		if not amount:
			return 0
		(stack, lvl, visited) = ([0], 0, set())
		while stack:
			new_lvl = []
			lvl += 1
			for i in stack:
				for c in coins:
					new = i + c
					if new == amount:
						return lvl
					if new not in visited:
						visited.add(new)
						new_lvl.append(new)
			if min(new_lvl) > amount:
				return -1
			stack = new_lvl


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		myQueue = [[0, 0]]
		reachedMap = {0}
		for (value, num_coins) in myQueue:
			for coin in coins:
				if coin + value in reachedMap:
					continue
				if coin + value == amount:
					return num_coins + 1
				if coin + value < amount:
					reachedMap.add(value + coin)
					myQueue.append([coin + value, num_coins + 1])
		return -1


class Solution:

	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0
		if not coins:
			return -1
		memo = {}
		stack = [amount]
		l = 0
		while stack:
			tmp = []
			for remain in stack:
				if remain < 0:
					continue
				for coin in coins:
					nxt = remain - coin
					if nxt == 0:
						return l + 1
					if nxt in memo:
						continue
					else:
						memo[nxt] = 1
					tmp += [nxt]
			stack = tmp
			l += 1
		return -1