Given an array cost[] of positive integers of size N and an integer W, cost[i] represents the cost of i kg packet of oranges, the task is to find the minimum cost to buy W kgs of oranges. If it is not possible to buy exactly W kg oranges then the output will be -1
Note:
1. cost[i] = -1 means that i kg packet of orange is unavailable
2.  It may be assumed that there is infinite supply of all available packet types.
Example 1:
Input: N = 5, arr[] = {20, 10, 4, 50, 100}
W = 5
Output: 14
Explanation: choose two oranges to minimize 
cost. First orange of 2Kg and cost 10. 
Second orange of 3Kg and cost 4. 
Example 2:
Input: N = 5, arr[] = {-1, -1, 4, 3, -1}
W = 5
Output: -1
Explanation: It is not possible to buy 5 
kgs of oranges
Your Task:  
You don't need to read input or print anything. Complete the function minimumCost() which takes N, W, and array cost as input parameters and returns the minimum value.
Expected Time Complexity: O(N*W)
Expected Auxiliary Space: O(N*W)
Constraints:
1 ≤ N, W ≤ 2*10^{2}
-1 ≤ cost[i] ≤ 10^{5}
cost[i] ≠ 0

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def minimumCost(self, cost, n, W):

        # code here

Solutions:
class Solution:

	def minimumCost(self, cost, n, W):

		def go(ind, currw):
			if currw > W:
				return 10 ** 18
			if ind == n:
				if currw == W:
					return 0
				return 10 ** 18
			if dp[ind][currw] != -1:
				return dp[ind][currw]
			c1 = 10 ** 18
			if cost[ind] != -1:
				c1 = cost[ind] + go(ind, currw + ind + 1)
			c2 = go(ind + 1, currw)
			ans = min(c1, c2)
			dp[ind][currw] = ans
			return ans
		dp = []
		for i in range(n):
			x = []
			for j in range(W + 1):
				x.append(-1)
			dp.append(x)
		ans1 = go(0, 0)
		if ans1 == 10 ** 18:
			return -1
		return ans1


class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[100000000.0] * (W + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(W + 1):
				if i == 0 and j == 0:
					dp[i][j] = 0
				elif cost[i - 1] == -1:
					dp[i][j] = dp[i - 1][j]
				elif i <= j:
					dp[i][j] = min(cost[i - 1] + dp[i][j - i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[n][W] == 100000000.0:
			return -1
		return dp[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		dp = {}

		def fun(i, W):
			if i < 0:
				if W == 0:
					return 0
				return 100000000.0
			if (i, W) in dp:
				return dp[i, W]
			take = 100000000.0
			if cost[i] == -1:
				return fun(i - 1, W)
			if i + 1 <= W:
				take = cost[i] + fun(i, W - (i + 1))
			not_take = fun(i - 1, W)
			dp[i, W] = min(take, not_take)
			return dp[i, W]
		res = fun(n - 1, W)
		if res == 100000000.0:
			return -1
		return res


class Solution:

	def minimumCost(self, cost, n, W):
		stateMap = [float('inf') for _ in range(W + 1)]
		stateMap[0] = 0
		for i in range(1, n + 1):
			if i > W:
				break
			for w in range(1, W + 1):
				if cost[i - 1] != -1:
					if stateMap[w - i] != -1:
						stateMap[w] = min(stateMap[w - i] + cost[i - 1], stateMap[w])
		return stateMap[-1] if stateMap[-1] != float('inf') else -1


class Solution:

	def minimumCost(self, arr, n, W):
		wt = list()
		val = list()
		for i in range(n):
			if arr[i] != -1:
				wt.append(i + 1)
				val.append(arr[i])
		n = len(wt)
		dp = [float('inf') for i in range(W + 1)]
		dp[0] = 0
		for i in range(1, W + 1):
			for j in range(n):
				if i - wt[j] >= 0:
					dp[i] = min(dp[i], dp[i - wt[j]] + val[j])
		return dp[W] if dp[W] != float('inf') else -1


class Solution:

	def minimumCost(self, cost, n, w):
		dp = [[-1] * (w + 1) for i in range(n)]

		def findmin(i, currw, w, n):
			if currw == w:
				return 0
			if i >= n or currw > w:
				return 999999999
			if dp[i][currw] != -1:
				return dp[i][currw]
			val = 999999999
			if cost[i] != -1:
				val = cost[i] + findmin(i, currw + i + 1, w, n)
				val = min(val, cost[i] + findmin(i + 1, currw + i + 1, w, n))
			val = min(val, findmin(i + 1, currw, w, n))
			dp[i][currw] = val
			return val
		val = findmin(0, 0, w, n)
		return val if val < 999999999 else -1


class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(W + 1):
				if j == 0:
					dp[i][j] = 0
				elif j >= i:
					dp[i][j] = min(dp[i][j], dp[i - 1][j], float('inf') if dp[i][j - i] == float('inf') or cost[i - 1] == -1 else dp[i][j - i] + cost[i - 1])
				else:
					dp[i][j] = min(dp[i][j], dp[i - 1][j])
		if dp[-1][-1] == float('inf'):
			return -1
		return dp[-1][-1]


class Solution:

	def minimumCost(self, cost, n, W):

		def func(cost, n, w, dp):
			if n == -1 and w == 0:
				return 0
			if w == 0:
				return 0
			if n < 0:
				return 10 ** 9
			if dp[n][w] != -1:
				return dp[n][w]
			if n + 1 > w or cost[n] == -1:
				dp[n][w] = func(cost, n - 1, w, dp)
				return dp[n][w]
			pick = cost[n] + func(cost, n, w - (n + 1), dp)
			notpick = func(cost, n - 1, w, dp)
			dp[n][w] = min(pick, notpick)
			return dp[n][w]
		dp = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		kk = func(cost, n - 1, W, dp)
		if kk == 10 ** 9:
			return -1
		return kk


class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[-1 for i in range(W + 1)] for i in range(n + 1)]
		ans = self.find(dp, cost, n, W)
		return ans if ans != float('inf') else -1

	def find(self, dp, cost, n, W):
		if W == 0:
			return 0
		if n == 0:
			return float('inf')
		if dp[n][W] != -1:
			return dp[n][W]
		dp[n][W] = self.find(dp, cost, n - 1, W)
		if n <= W and cost[n - 1] != -1:
			dp[n][W] = min(dp[n][W], cost[n - 1] + self.find(dp, cost, n, W - n))
		return dp[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		val = []
		w = [][:]
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				w.append(i + 1)
		n = len(val)
		t = [[0] * (W + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(W + 1):
				if i == 0:
					t[i][j] = 99999
				if j == 0 and i > 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if w[i - 1] > j:
					t[i][j] = t[i - 1][j]
				else:
					t[i][j] = min(val[i - 1] + t[i][j - w[i - 1]], t[i - 1][j])
		if t[n][W] == 99999:
			return -1
		return t[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		INT_MAX = 2 ** 63
		dp = [[INT_MAX] * (W + 1) for i in range(n + 1)]
		dp[0][0] = 0
		for i in range(1, n + 1):
			for j in range(0, W + 1):
				if j == 0:
					dp[i][j] = 0
				elif j < i or cost[i - 1] == -1:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
					if dp[i][j - i] != INT_MAX:
						dp[i][j] = min(dp[i][j], cost[i - 1] + dp[i][j - i])
		if dp[n][W] == INT_MAX:
			return -1
		return dp[n][W]


class Solution:

	def minimumCost(self, a, n, W):
		dpPrev = [float('inf') for _ in range(W + 1)]
		dp = [0] * (W + 1)
		for i in range(1, n + 1):
			for j in range(W + 1):
				if j == 0:
					dp[j] = 0
					continue
				dp[j] = dpPrev[j]
				if i <= j and a[i - 1] != -1:
					dp[j] = min(dp[j], a[i - 1] + dp[j - i])
			(dp, dpPrev) = (dpPrev, dp)
		return dpPrev[W] if dpPrev[W] != float('inf') else -1


INF = 1000000

class Solution:

	def minimumCost(self, cost, n, W):
		val = list()
		wt = list()
		size = 0
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				wt.append(i + 1)
				size += 1
		n = size
		min_cost = [[0 for i in range(W + 1)] for j in range(n + 1)]
		for i in range(W + 1):
			min_cost[0][i] = INF
		for i in range(1, n + 1):
			min_cost[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] > j:
					min_cost[i][j] = min_cost[i - 1][j]
				else:
					min_cost[i][j] = min(min_cost[i - 1][j], min_cost[i][j - wt[i - 1]] + val[i - 1])
		if min_cost[n][W] == INF:
			return -1
		else:
			return min_cost[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		table = [[-1] * (W + 1) for _ in range(n + 1)]

		def min_cost_oranges(cost, N, W):
			if W == 0:
				return 0
			if N == 0 or W < 0:
				return 1000000.0
			if table[N][W] == -1:
				if N > W or cost[N - 1] == -1:
					table[N][W] = min_cost_oranges(cost, N - 1, W)
				else:
					table[N][W] = min(min_cost_oranges(cost, N - 1, W), min_cost_oranges(cost, N, W - N) + cost[N - 1])
			return table[N][W]
		ans = min_cost_oranges(cost, n, W)
		return ans


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		wt = [i for i in range(1, n + 1)]
		dp = [[0 for i in range(W + 1)] for i in range(n + 1)]
		for j in range(W + 1):
			dp[0][j] = sys.maxsize
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if j >= wt[i - 1] and cost[i - 1] != -1:
					dp[i][j] = min(dp[i - 1][j], cost[i - 1] + dp[i][j - wt[i - 1]])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		(weights, values, size) = ([], [], 0)
		for i in range(n):
			if cost[i] != -1:
				weights.append(i + 1)
				values.append(cost[i])
				size += 1
		memo = {}

		def dp(i, w):
			if w == 0:
				return 0
			if i == size:
				return float('inf')
			key = (i, w)
			if key in memo:
				return memo[key]
			if weights[i] <= w:
				memo[key] = min(dp(i + 1, w), values[i] + dp(i, w - weights[i]))
			else:
				memo[key] = dp(i + 1, w)
			return memo[key]
		res = dp(0, W)
		return res if res != float('inf') else -1


class Solution:

	def minimumCost(self, cost, n, W):
		dp = {}

		def fun(i, w):
			if i == n + 1:
				if w == 0:
					return 0
				else:
					return 10000000
			if w == 0:
				return 0
			if (i, w) in dp:
				return dp[i, w]
			if i <= w and cost[i - 1] != -1:
				dp[i, w] = min(cost[i - 1] + fun(i, w - i), fun(i + 1, w))
			else:
				dp[i, w] = fun(i + 1, w)
			return dp[i, w]
		t = fun(1, W)
		if t >= 10000000:
			return -1
		return t


from collections import defaultdict

class Solution:

	def minimumCost(self, cost, n, W):
		d = defaultdict(lambda : float('inf'))
		d[0] = 0
		for i in range(1, W + 1):
			mini = float('inf')
			for (j, item) in enumerate(cost):
				if item == -1:
					continue
				mini = min(mini, d[i - j - 1] + item)
			d[i] = mini
		return d[W] if d[W] != float('inf') else -1


import sys

class Solution:

	def recursion(self, n, W, cost, wt, dp):
		if W == 0:
			return 0
		if n < 0 or W < 0:
			return sys.maxsize
		if cost[n - 1] < 0:
			dp[n][W] = self.recursion(n - 1, W, cost, wt, dp)
		if dp[n][W] != -1:
			return dp[n][W]
		if W >= wt[n - 1]:
			dp[n][W] = min(cost[n - 1] + self.recursion(n, W - wt[n - 1], cost, wt, dp), self.recursion(n - 1, W, cost, wt, dp))
			return dp[n][W]
		dp[n][W] = self.recursion(n - 1, W, cost, wt, dp)
		return dp[n][W]

	def minimumCost(self, cost, n, W):
		dp = [[-1 for i in range(W + 1)] for i in range(n + 1)]
		wt = [i for i in range(1, n + 1)]
		return self.recursion(n, W, cost, wt, dp)


class Solution:

	def minimumCost(self, cost, n, w):
		k = 1000000
		t = [[0] * (w + 1) for i in range(n + 1)]
		wt = [i for i in range(1, n + 1)]
		for j in range(w + 1):
			t[0][j] = k
		for i in range(1, n + 1):
			for j in range(1, w + 1):
				if wt[i - 1] <= j and cost[i - 1] != -1:
					t[i][j] = min(cost[i - 1] + t[i][j - wt[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[n][w] == k:
			return -1
		else:
			return t[n][w]


class Solution:

	def solve(self, n, cost, wt, dp):
		if n == -1 and wt == 0:
			return 0
		if w == 0:
			return 0
		if n == -1:
			return 99999999
		if dp[n][wt] != -1:
			return dp[n][wt]
		if cost[n] == -1 or n + 1 > wt:
			dp[n][wt] = self.solve(n - 1, cost, wt, dp)
			return dp[n][wt]
		incl = cost[n] + self.solve(n, cost, wt - (n + 1), dp)
		excl = self.solve(n - 1, cost, wt, dp)
		dp[n][wt] = min(incl, excl)
		return dp[n][wt]

	def minimumCost(self, cost, n, W):
		dp = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		ans = self.solve(n - 1, cost, W, dp)
		if ans == 99999999:
			return -1
		else:
			return ans


import sys

def helper(cost, weight, n, w, dp):
	if w == 0:
		return 0
	if w < 0 or n <= 0:
		return sys.maxsize
	if dp[n][w] != -1:
		return dp[n][w]
	if cost[n - 1] < 0:
		dp[n][w] = helper(cost, weight, n - 1, w, dp)
		return dp[n][w]
	if weight[n - 1] <= w:
		dp[n][w] = min(cost[n - 1] + helper(cost, weight, n, w - weight[n - 1], dp), helper(cost, weight, n - 1, w, dp))
		return dp[n][w]
	dp[n][w] = helper(cost, weight, n - 1, w, dp)
	return dp[n][w]

class Solution:

	def minimumCost(self, cost, N, W):
		weight = [i for i in range(1, N + 1)]
		dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
		res = helper(cost, weight, N, W, dp)
		return -1 if res >= sys.maxsize else res


class Solution:

	def minimumCost(self, cost, n, w):
		dp = [float('inf')] * (w + 1)
		dp[0] = 0
		for i in range(1, w + 1):
			for j in range(i):
				if j >= n or i - j - 1 < 0 or cost[j] == -1:
					continue
				dp[i] = min(dp[i], dp[i - j - 1] + cost[j])
		return -1 if dp[w] == float('inf') else dp[w]


from math import inf

class Solution:

	def minimumCost(self, cost, n, wt):
		dp = [[inf for w in range(wt + 1)] for i in range(2)]
		for i in range(n, 0, -1):
			dp[0][0] = 0
			for w in range(1, wt + 1):
				dp[0][w] = inf
				if i <= w:
					if cost[i - 1] != -1:
						dp[0][w] = min(dp[0][w], cost[i - 1] + dp[1][w - i], cost[i - 1] + dp[0][w - i])
					dp[0][w] = min(dp[0][w], dp[1][w])
			(dp[0], dp[1]) = (dp[1], dp[0])
		return dp[1][wt] if dp[1][wt] != inf else -1


class Solution:

	def minimumCost(self, cost, n, W):
		costs = []
		weights = []
		for i in range(len(cost)):
			if cost[i] != -1:
				costs.append(cost[i])
				weights.append(i + 1)
		dp = [[float('inf') for _ in range(W + 1)] for _ in range(len(costs))]
		for r in range(len(costs)):
			dp[r][0] = 0
		for i in range(len(costs)):
			for j in range(1, W + 1):
				if j - weights[i] >= 0:
					dp[i][j] = min(dp[i][j], costs[i] + dp[i][j - weights[i]])
				if i > 0:
					dp[i][j] = min(dp[i][j], dp[i - 1][j])
		return dp[len(costs) - 1][W] if dp[len(costs) - 1][W] != float('inf') else -1


from math import inf

class Solution:

	def __min_cost_helper(self, i, w, cost, n):
		if w == 0:
			return 0
		if i == n + 1:
			return inf
		if self.dp[w][i] == None:
			self.dp[w][i] = inf
			if i <= w:
				if cost[i - 1] != -1:
					self.dp[w][i] = min(self.dp[w][i], cost[i - 1] + self.__min_cost_helper(i + 1, w - i, cost, n), cost[i - 1] + self.__min_cost_helper(i, w - i, cost, n))
				self.dp[w][i] = min(self.dp[w][i], self.__min_cost_helper(i + 1, w, cost, n))
		return self.dp[w][i]

	def minimumCost(self, cost, n, w):
		self.dp = [[None for i in range(len(cost) + 1)] for j in range(w + 1)]
		res = self.__min_cost_helper(1, w, cost, len(cost))
		return res if res != inf else -1


class Solution:

	def minimumCost(self, cost, n, W):
		arr = cost
		dp = [10 ** 6] * max(n + 1, W + 1)
		for i in range(1, W + 1):
			if i <= n:
				dp[i] = arr[i - 1]
			for j in range(i):
				if dp[j] != -1 and dp[i - j] != -1:
					dp[i] = min(dp[i], dp[j] + dp[i - j])
		if dp[W] == 10 ** 6:
			return -1
		else:
			return dp[W]


import sys

class Solution:

	def solve(self, cost, idx, w, dp):
		if w == 0:
			return 0
		if idx <= -1:
			return 1000000000.0
		if dp[idx][w] != -1:
			return dp[idx][w]
		include = 1000000000.0
		if cost[idx] != -1 and idx + 1 <= w:
			include = cost[idx] + self.solve(cost, idx, w - (idx + 1), dp)
		exclude = 0 + self.solve(cost, idx - 1, w, dp)
		dp[idx][w] = min(include, exclude)
		return dp[idx][w]

	def minimumCost(self, cost, n, W):
		dp = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		ans = self.solve(cost, n - 1, w, dp)
		if ans >= 1000000000.0:
			return -1
		return ans


import sys

class Solution:

	def solve(self, cost, idx, w, dp):
		if idx == -1:
			if w == 0:
				return 0
			else:
				return 1000000000.0
		if w == 0:
			return 0
		if dp[idx][w] != -1:
			return dp[idx][w]
		if cost[idx] == -1 or idx + 1 > w:
			dp[idx][w] = self.solve(cost, idx - 1, w, dp)
			return dp[idx][w]
		include = cost[idx] + self.solve(cost, idx, w - (idx + 1), dp)
		exclude = 0 + self.solve(cost, idx - 1, w, dp)
		dp[idx][w] = min(include, exclude)
		return dp[idx][w]

	def tabular(self, cost, n, w):
		dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
		for i in range(w + 1):
			if i == 0:
				dp[-1][i] = 0
			else:
				dp[-1][i] = 1000000000.0
		for i in range(1, n + 1):
			dp[i][0] = 0
		for idx in range(n):
			for wt in range(w + 1):
				if cost[idx] == -1 or idx + 1 > wt:
					dp[idx][wt] = dp[idx - 1][wt]
				else:
					include = cost[idx] + dp[idx][wt - (idx + 1)]
					exclude = 0 + dp[idx - 1][wt]
					dp[idx][wt] = min(include, exclude)
		return dp[n - 1][w]

	def minimumCost(self, cost, n, W):
		return self.tabular(cost, n, W)
		dp = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		ans = self.solve(cost, n - 1, w, dp)
		if ans >= 1000000000.0:
			return -1
		return ans


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		val = list()
		wt = list()
		size = 0
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				wt.append(i + 1)
				size += 1
		n = size
		min_cost = [[0 for i in range(W + 1)] for j in range(n + 1)]
		for i in range(W + 1):
			min_cost[0][i] = float('inf')
		for i in range(1, n + 1):
			min_cost[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] > j:
					min_cost[i][j] = min_cost[i - 1][j]
				else:
					min_cost[i][j] = min(min_cost[i - 1][j], min_cost[i][j - wt[i - 1]] + val[i - 1])
		if min_cost[n][W] == float('inf'):
			return -1
		else:
			return min_cost[n][W]


import sys

class Solution:

	def minimumCost(self, cost, n, w):
		c = [[float('inf') for _ in range(n)] for _ in range(w + 1)]
		c[0] = [0] * n
		for i in range(n):
			for j in range(1, w + 1):
				x = c[j][i - 1] if i >= 1 else float('inf')
				if j < i + 1 or cost[i] == -1:
					c[j][i] = x
				else:
					c[j][i] = min(c[j - i - 1][i] + cost[i], x)
		return c[w][n - 1]


import sys

class Solution:

	def helper(self, ind, W, cost, N, dp):
		if ind == 0:
			if cost[0] != -1:
				return W * cost[0]
			return 1000000000.0
		if W == 0:
			return 0
		if dp[ind][W] != -1:
			return dp[ind][W]
		if cost[ind] == -1:
			return self.helper(ind - 1, W, cost, N, dp)
		not_take = self.helper(ind - 1, W, cost, N, dp)
		take = sys.maxsize
		if W >= ind + 1:
			take = cost[ind] + self.helper(ind, W - (ind + 1), cost, N, dp)
		dp[ind][W] = min(take, not_take)
		return dp[ind][W]

	def minimumCost(self, cost, n, W):
		dp = [[-1 for i in range(W + 1)] for j in range(n)]
		ways = self.helper(n - 1, W, cost, n, dp)
		if ways >= 1000000000.0:
			return -1
		return ways


import sys
import math

class Solution:

	def minimumCost(self, cost, n, W):
		dp = [math.inf for i in range(W + 1)]
		dp[0] = 0
		for w in range(1, n + 1):
			if cost[w - 1] == -1:
				continue
			for i in range(w, W + 1):
				if dp[i - w] != math.inf:
					dp[i] = min(dp[i], cost[w - 1] + dp[i - w])
		if dp[-1] != math.inf:
			return dp[-1]
		return -1


import sys

class Solution:

	def answer(self, i, target, cost, weight, n, dp):
		if target == 0:
			return 0
		if i == n - 1:
			if cost[i] == -1:
				return float('inf')
			if target % weight[n - 1] == 0:
				return target // weight[n - 1] * cost[n - 1]
			else:
				return float('inf')
		if dp[i][target] != -1:
			return dp[i][target]
		temp1 = float('inf')
		if i + 1 <= target:
			if cost[i] == -1:
				temp1 = float('inf')
			else:
				temp1 = cost[i] + self.answer(i, target - weight[i], cost, weight, n, dp)
		temp2 = self.answer(i + 1, target, cost, weight, n, dp)
		dp[i][target] = min(temp1, temp2)
		return dp[i][target]

	def minimumCost(self, cost, n, W):
		weight = [i + 1 for i in range(n)]
		dp = [[0 for x in range(W + 1)] for x in range(n)]
		for target in range(W + 1):
			if cost[n - 1] == -1:
				dp[n - 1][target] = float('inf')
			elif target % weight[n - 1] == 0:
				dp[n - 1][target] = target // weight[n - 1] * cost[n - 1]
			else:
				dp[n - 1][target] = float('inf')
		for i in range(n - 2, -1, -1):
			for target in range(1, W + 1):
				temp1 = float('inf')
				if i + 1 <= target:
					if cost[i] == -1:
						temp1 = float('inf')
					else:
						temp1 = cost[i] + dp[i][target - weight[i]]
				temp2 = dp[i + 1][target]
				dp[i][target] = min(temp1, temp2)
		if dp[0][W] != float('inf'):
			return dp[0][W]
		else:
			return -1


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		(val, wt, size) = ([], [], 0)
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				wt.append(i + 1)
				size += 1
		n = size
		dp = [[float('inf') for _ in range(W + 1)] for _ in range(n + 1)]
		for r in range(1, n + 1):
			dp[r][0] = 0
			for c in range(1, W + 1):
				if wt[r - 1] > c:
					dp[r][c] = dp[r - 1][c]
				else:
					dp[r][c] = min(dp[r - 1][c], val[r - 1] + dp[r][c - wt[r - 1]])
		return dp[-1][-1] if dp[-1][-1] != float('inf') else -1


class Solution:

	def minimumCost(self, cost, n, W):
		dp = []
		for i in range(n + 1):
			dp.append([float('inf')] * (W + 1))
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if cost[i - 1] == -1:
					dp[i][j] = dp[i - 1][j]
					continue
				if j - i >= 0:
					dp[i][j] = min(dp[i - 1][j], dp[i][j - i] + cost[i - 1])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[-1][-1] == float('inf'):
			return -1
		return dp[-1][-1]


INF = 10 ** 9
import sys
from collections import defaultdict

class Solution:

	def minimumCost(self, cost, n, w):
		inf = lambda : INF
		hmap = defaultdict(inf)
		hmap[0] = 0
		for i in range(1, w + 1):
			for j in range(1, n + 1):
				if cost[j - 1] > 0:
					hmap[i] = min(hmap[i], hmap[i - j] + cost[j - 1])
		return hmap[w] if hmap[w] < INF else -1


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[0 for _ in range(1000)] for i in range(1000)]

		def func(cost, n, W, dp):
			if n == -1 and W == 0:
				return 0
			if n == -1:
				return 1000000007
			if W == 0:
				return 0
			if dp[n][W] != 0:
				return dp[n][W]
			if n + 1 > W or cost[n] == -1:
				dp[n][W] = func(cost, n - 1, W, dp)
				return dp[n][W]
			elif n + 1 <= W:
				dp[n][W] = min(cost[n] + func(cost, n, W - (n + 1), dp), func(cost, n - 1, W, dp))
				return dp[n][W]
		x = func(cost, n - 1, W, dp)
		if x >= 1000000007:
			return -1
		else:
			return x


class Solution:

	def find(self, W, cost, curr):
		if W == 0:
			return 0
		elif curr == 0:
			return 10 ** 9
		elif self.memo[curr][W] != -1:
			return self.memo[curr][W]
		elif cost[curr - 1] == -1 or W < curr:
			self.memo[curr][W] = self.find(W, cost, curr - 1)
			return self.memo[curr][W]
		else:
			x = cost[curr - 1] + self.find(W - curr, cost, curr)
			y = self.find(W, cost, curr - 1)
			self.memo[curr][W] = min(x, y)
			return self.memo[curr][W]

	def minimumCost(self, cost, n, W):
		self.memo = [[-1 for _ in range(W + 1)] for _ in range(len(cost) + 1)]
		self.find(W, cost, n)
		if self.memo[n][W] >= 10 ** 9:
			return -1
		return self.memo[n][W]


class Solution:

	def minimumCost(self, cost, n, W):
		(wt, val) = ([], [])
		size = 0
		for (i, c) in enumerate(cost):
			if c != -1:
				wt.append(i + 1)
				val.append(c)
				size += 1
		n = size
		dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
		for i in range(W + 1):
			dp[0][i] = float('inf')
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = min(dp[i - 1][j], val[i - 1] + dp[i][j - wt[i - 1]])
		return dp[n][W] if dp[n][W] != float('inf') else -1


import sys
sys.setrecursionlimit(10 ** 6)

def f(cost, wt, N, summ, idx, dp):
	if summ == 0:
		return 0
	if idx == N:
		return int(1000000000.0)
	if dp[idx][summ] != -1:
		return dp[idx][summ]
	ans = 0
	if wt[idx] <= summ:
		ans = min(cost[idx] + f(cost, wt, N, summ - wt[idx], idx, dp), f(cost, wt, N, summ, idx + 1, dp))
	else:
		ans = f(cost, wt, N, summ, idx + 1, dp)
	dp[idx][summ] = ans
	return ans

class Solution:

	def minimumCost(self, cost, n, W):
		val = list()
		wt = list()
		size = 0
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				wt.append(i + 1)
				size += 1
		n = size
		dp = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		ans = f(val, wt, n, W, 0, dp)
		if ans >= int(1000000000.0):
			return -1
		return ans


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		data = []
		for i in range(n + 1):
			data.append([0] * (W + 1))
		for rowN in range(n + 1):
			for colW in range(W + 1):
				if colW == 0:
					data[rowN][colW] = 0
				elif rowN == 0:
					data[rowN][colW] = float('inf')
				elif colW - rowN >= 0 and cost[rowN - 1] != -1:
					data[rowN][colW] = min(data[rowN - 1][colW], cost[rowN - 1] + data[rowN][colW - rowN])
				else:
					data[rowN][colW] = data[rowN - 1][colW]
		if data[rowN][colW] == 0:
			return -1
		return data[rowN][colW]


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		dp = [float('inf')] * (W + 1)
		dp[0] = 0
		for i in range(n):
			if cost[i] == -1:
				continue
			for j in range(1, W + 1):
				if j >= i + 1:
					dp[j] = min(dp[j], cost[i] + dp[j - (i + 1)])
		return dp[-1]


import sys
INT_MAX = sys.maxsize

class Solution:

	def min_cost_util(self, idx, W, wt, val, n, dp):
		if idx == n:
			return INT_MAX
		if W == 0:
			return 0
		if dp[idx][W] != -1:
			return dp[idx][W]
		not_pick = self.min_cost_util(idx + 1, W, wt, val, n, dp)
		pick = INT_MAX
		if wt[idx] <= W:
			pick = val[idx] + self.min_cost_util(idx, W - wt[idx], wt, val, n, dp)
		dp[idx][W] = min(pick, not_pick)
		return dp[idx][W]

	def minimumCost(self, cost, n, W):
		wt = []
		val = []
		for i in range(n):
			if cost[i] != -1:
				wt.append(i + 1)
				val.append(cost[i])
		n = len(wt)
		dp = [[-1 for _ in range(W + 1)] for _ in range(n + 1)]
		for j in range(W + 1):
			dp[0][j] = INT_MAX
		for i in range(1, n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] <= j:
					dp[i][j] = min(dp[i - 1][j], val[i - 1] + dp[i][j - wt[i - 1]])
				else:
					dp[i][j] = dp[i - 1][j]
		res = dp[n][W]
		if res == INT_MAX:
			return -1
		return res


class Solution:

	def minimumCost(self, cost, N, W):
		dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			for j in range(W + 1):
				if i == 0:
					dp[i][j] = 10 ** 99
				elif j == 0:
					dp[i][j] = 0
				elif i <= j and cost[i - 1] != -1:
					dp[i][j] = min(cost[i - 1] + dp[i][j - i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[N][W] == 10 ** 99:
			return -1
		else:
			return dp[N][W]


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[float('inf') for i in range(W + 1)] for j in range(n + 1)]
		dp[n][0] = 0
		for ind in range(n - 1, -1, -1):
			for tar in range(W + 1):
				ntake = dp[ind + 1][tar]
				take = float('inf')
				if tar >= ind and cost[ind] > 0:
					take = cost[ind] + dp[ind][tar - ind - 1]
				dp[ind][tar] = min(ntake, take)
		return dp[0][W] if dp[0][W] != float('inf') else -1

		def bagcost(ind, tar):
			if ind == n:
				if tar == 0:
					return 0
				return float('inf')
			if dp[ind][tar] != float('inf'):
				return dp[ind][tar]
			ntake = bagcost(ind + 1, tar)
			take = float('inf')
			if ind <= tar and cost[ind] > 0:
				take = cost[ind] + bagcost(ind, tar - ind - 1)
			dp[ind][tar] = min(take, ntake)
			return dp[ind][tar]
		dp = [[float('inf') for i in range(W + 1)] for j in range(n + 1)]
		res = bagcost(0, W)
		return res if res != float('inf') else -1
		val = list()
		wt = list()
		size = 0
		for i in range(n):
			if cost[i] != -1:
				val.append(cost[i])
				wt.append(i + 1)
				size += 1
		n = size
		min_cost = [[0 for i in range(W + 1)] for j in range(n + 1)]
		for i in range(W + 1):
			min_cost[0][i] = float('inf')
		for i in range(1, n + 1):
			min_cost[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] > j:
					min_cost[i][j] = min_cost[i - 1][j]
				else:
					min_cost[i][j] = min(min_cost[i - 1][j], min_cost[i][j - wt[i - 1]] + val[i - 1])
		if min_cost[n][W] == float('inf'):
			return -1
		else:
			return min_cost[n][W]


import sys

class Solution:

	def minimumCost(self, arr, n, w):
		dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
		for i in range(w + 1):
			dp[0][i] = float('inf')
		for i in range(1, n + 1):
			for j in range(1, w + 1):
				if i <= j and arr[i - 1] != -1:
					dp[i][j] = min(arr[i - 1] + dp[i][j - i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[n][w] == float('inf'):
			return -1
		return dp[n][w]


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def minimumCost(self, cost, n, W):

		def find():
			curr = [0 for _ in range(W + 1)]
			nxt = [0 for _ in range(W + 1)]
			for i in range(W + 1):
				nxt[i] = 1000000000.0
			nxt[0] = 0
			for i in range(n - 1, -1, -1):
				for w in range(0, W + 1):
					include = 1000000000.0
					if i + 1 <= w and cost[i] != -1:
						include = cost[i] + curr[w - (i + 1)]
					exclude = nxt[w]
					curr[w] = min(include, exclude)
				nxt = curr.copy()
			if nxt[W] >= 1000000000.0:
				return -1
			return nxt[W]
		return find()


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def minimumCost(self, cost, n, W):
		dp = [[-1 for _ in range(W + 1)] for _ in range(n)]

		def find(i, w):
			if i >= n and w == 0:
				return 0
			if i >= n:
				return 1000000000.0
			if w == 0:
				return 0
			if dp[i][w] != -1:
				return dp[i][w]
			if i + 1 > w or cost[i] == -1:
				dp[i][w] = find(i + 1, w)
				return dp[i][w]
			include = cost[i] + find(i, w - (i + 1))
			exclude = find(i + 1, w)
			dp[i][w] = min(include, exclude)
			return dp[i][w]
		ans = find(0, W)
		if ans >= 1000000000.0:
			return -1
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def solve(self, cost, W, i, dp):
		if W == 0:
			return 0
		if W < 0:
			return 1000000000
		if i >= len(cost):
			return 1000000000
		if (i, W) in dp:
			return dp[i, W]
		if W >= i + 1 and cost[i] != -1:
			dp[i, W] = min(cost[i] + self.solve(cost, W - (i + 1), i, dp), self.solve(cost, W, i + 1, dp))
			return dp[i, W]
		else:
			dp[i, W] = self.solve(cost, W, i + 1, dp)
			return dp[i, W]

	def minimumCost(self, cost, n, W):
		dp = {}
		ans = self.solve(cost, W, 0, dp)
		if ans >= 100000000:
			return -1
		return ans


import sys

class Solution:

	def minimumCost(self, val, n, W):
		arr = []
		value = []
		for i in range(n):
			if val[i] != -1:
				arr.append(i + 1)
				value.append(val[i])
		n = len(arr)
		t = [[-1 for i in range(W + 1)] for j in range(n + 1)]
		for j in range(W + 1):
			t[0][j] = 10 ** 9
		for i in range(n + 1):
			t[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if arr[i - 1] <= j:
					include = value[i - 1] + t[i][j - arr[i - 1]]
					exclude = t[i - 1][j]
					t[i][j] = min(include, exclude)
				else:
					exclude = t[i - 1][j]
					t[i][j] = exclude
		if t[n][W] == 10 ** 9:
			return -1
		return t[n][W]


import sys

class Solution:

	def minimumCost(self, cost, n, W):
		arr = []
		value = []
		for i in range(n):
			if cost[i] != -1:
				arr.append(i + 1)
				value.append(cost[i])
		t = [[-1 for i in range(W + 1)] for j in range(len(arr) + 1)]
		c = self.solve(W, arr, value, len(arr), t)
		if c == 10 ** 9:
			return -1
		return c

	def solve(self, W, arr, value, n, t):
		if W == 0:
			return 0
		if W < 0 or n <= 0:
			return 10 ** 9
		if t[n][W] != -1:
			return t[n][W]
		if W - arr[n - 1] >= 0:
			incl = value[n - 1] + self.solve(W - arr[n - 1], arr, value, n, t)
			excl = self.solve(W, arr, value, n - 1, t)
			t[n][W] = min(incl, excl)
			return min(incl, excl)
		else:
			excl = self.solve(W, arr, value, n - 1, t)
			t[n][W] = excl
			return excl


from sys import maxsize

class Solution:

	def minimumCost(self, cost, n, w):
		dp = [[maxsize for _ in range(w + 1)] for _ in range(n)]
		for i in range(n):
			dp[i][0] = 0
		for i in range(n):
			for j in range(1, w + 1):
				if cost[i] == -1:
					dp[i][j] = dp[i - 1][j] if i >= 1 else maxsize
					continue
				if i == 0:
					dp[i][j] = dp[i][j - i - 1] + cost[i]
					continue
				elif i + 1 <= j:
					dp[i][j] = min(dp[i][j - i - 1] + cost[i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n - 1][w] if dp[n - 1][w] != maxsize else -1


import sys

class Solution:

	def solve(self, arr, n, w, dp):
		if n == 0:
			if w == 0:
				return 0
			elif arr[0] != -1:
				return w * arr[0]
			else:
				return 1000000000.0
		if dp[n][w] != -1:
			return dp[n][w]
		if arr[n] > 0 and n + 1 <= w:
			dp[n][w] = min(arr[n] + self.solve(arr, n, w - (n + 1), dp), self.solve(arr, n - 1, w, dp))
		else:
			dp[n][w] = self.solve(arr, n - 1, w, dp)
		return dp[n][w]

	def minimumCost(self, cost, n, W):
		dp = [[-1 for j in range(W + 1)] for i in range(n)]
		ans = self.solve(cost, n - 1, W, dp)
		if ans >= 1000000000.0:
			return -1
		return ans