Given an integer N denoting the Length of a line segment. You need to cut the line segment in such a way that the cut length of a line segment each time is either x , y or z. Here x, y, and z are integers.
After performing all the cut operations, your total number of cut segments must be maximum.
Note: if no segment can be cut then return 0.
Example 1:
Input:
N = 4
x = 2, y = 1, z = 1
Output: 4
Explanation:Total length is 4, and the cut
lengths are 2, 1 and 1.  We can make
maximum 4 segments each of length 1.
Example 2:
Input:
N = 5
x = 5, y = 3, z = 2
Output: 2
Explanation: Here total length is 5, and
the cut lengths are 5, 3 and 2. We can
make two segments of lengths 3 and 2.
Your Task:
You only need to complete the function maximizeTheCuts() that takes n, x, y, z as parameters and returns max number cuts.
Expected Time Complexity : O(N)
Expected Auxiliary Space: O(N)
Constraints
1 <= N, x, y, z <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3





class Solution:

    

    #Function to find the maximum number of cuts.

    def maximizeTheCuts(self,n,x,y,z):

        #code here

Solutions:
import sys

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for i in range(n):
			if dp[i] == -1:
				continue
			if i + x <= n:
				dp[i + x] = max(dp[i + x], 1 + dp[i])
			if i + y <= n:
				dp[i + y] = max(dp[i + y], 1 + dp[i])
			if i + z <= n:
				dp[i + z] = max(dp[i + z], 1 + dp[i])
		return dp[n] if dp[n] != -1 else 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			if i - x >= 0 and dp[i - x] != -1:
				dp[i] = max(dp[i], dp[i - x] + 1)
			if i - y >= 0 and dp[i - y] != -1:
				dp[i] = max(dp[i], dp[i - y] + 1)
			if i - z >= 0 and dp[i - z] != -1:
				dp[i] = max(dp[i], dp[i - z] + 1)
		if dp[n] <= 0:
			return 0
		else:
			return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [float('-inf')] * (n + 1)
		dp[0] = 0
		l = sorted(set([x, y, z]))
		for i in range(1, n + 1):
			for e in l:
				if i - e < 0:
					continue
				dp[i] = max(dp[i], dp[i - e] + 1)
		return dp[n] if dp[n] != float('-inf') else 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for i in range(n + 1):
			if dp[i] == -1:
				continue
			for choice in [x, y, z]:
				if i + choice <= n:
					dp[i + choice] = max(dp[i + choice], dp[i] + 1)
		if dp[n] == -1:
			dp[n] = 0
		return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		MIN = float('-inf')
		dp = [MIN] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			max_cuts = MIN
			if i >= x:
				max_cuts = max(max_cuts, dp[i - x])
			if i >= y:
				max_cuts = max(max_cuts, dp[i - y])
			if i >= z:
				max_cuts = max(max_cuts, dp[i - z])
			if max_cuts >= 0:
				dp[i] = 1 + max_cuts
		return 0 if dp[-1] == MIN else dp[-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def fun(self, n, x, y, z, dp):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		a = self.fun(n - x, x, y, z, dp)
		b = self.fun(n - y, x, y, z, dp)
		c = self.fun(n - z, x, y, z, dp)
		if a == 0 and b == 0 and (c == 0):
			return 0
		dp[n] = 1 + max(a, b, c)
		return dp[n]

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(10 ** 4 + 1)]
		dp[0] = 0
		for i in range(min(x, y, z), n + 1):
			res = -1
			if i - x >= 0:
				res = max(res, dp[i - x])
			if i - y >= 0:
				res = max(res, dp[i - y])
			if i - z >= 0:
				res = max(res, dp[i - z])
			if res >= 0:
				dp[i] = res + 1
		if dp[n] == -1:
			return 0
		return dp[n]


import sys

class Solution:

	def rec_sol(self, n, x, y, z):
		if n < 0:
			return sys.minsize
		if n == 0:
			return 0
		return max(max(self.rec_sol(n - x, x, y, z), self.rec_sol(n - y, x, y, z)), self.rec_sol(n - z, x, y, z))

	def dp_sol(self, n, x, y, z):
		ans = [-999999] * (n + 1)
		ans[0] = 0
		cuts = [x, y, z]
		for i in range(1, n + 1):
			for cut in cuts:
				if i >= cut:
					ans[i] = max(ans[i], ans[i - cut] + 1)
		return ans[n]

	def maximizeTheCuts(self, n, x, y, z):
		ans = self.dp_sol(n, x, y, z)
		if ans < 0:
			return 0
		return ans


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = []
		for i in range(n + 1):
			dp.append(0)
		dp[0] = 0
		coin = [x, y, z]
		for i in range(1, n + 1):
			for j in range(3):
				if coin[j] <= i:
					res = dp[i - coin[j]]
					if res + 1 > dp[i] and (dp[i - coin[j]] > 0 or i - coin[j] == 0):
						dp[i] = res + 1
		return dp[n]


import sys
sys.setrecursionlimit(10010)

class Solution:

	def solve(self, n, x, y, z, dp):
		if n == 0:
			return 0
		if n < 0:
			return float('-inf')
		if dp[n] != -1:
			return dp[n]
		a = self.solve(n - x, x, y, z, dp)
		ans_a = a + 1
		b = self.solve(n - y, x, y, z, dp)
		ans_b = b + 1
		c = self.solve(n - z, x, y, z, dp)
		ans_c = c + 1
		dp[n] = max(ans_a, ans_b, ans_c)
		return dp[n]

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]
		ans = self.solve(n, x, y, z, dp)
		if ans < 0:
			return 0
		return ans


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		stateMap = [0] * (n + 1)
		stateMap[0] = 1
		for l in [x, y, z]:
			for i in range(l, n + 1):
				if stateMap[i - l]:
					stateMap[i] = max(1 + stateMap[i - l], stateMap[i])
		return stateMap[n] - 1 if stateMap[n] else 0


import math

class Solution:

	def maximizeTheCutsHelper(self, n, x, y, z, dp_mem):
		if n == 0:
			return 0
		if n < 0:
			return -math.inf
		if dp_mem[n] != -1:
			return dp_mem[n]
		ans = -math.inf
		ans = max(ans, 1 + max(self.maximizeTheCutsHelper(n - x, x, y, z, dp_mem), self.maximizeTheCutsHelper(n - y, x, y, z, dp_mem), self.maximizeTheCutsHelper(n - z, x, y, z, dp_mem)))
		dp_mem[n] = ans
		return ans

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-math.inf] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			for val in [x, y, z]:
				if i - val >= 0:
					dp[i] = max(dp[i], dp[i - val] + 1)
		return 0 if dp[-1] == -math.inf else dp[-1]


import math

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			if x <= i:
				dp[i] = dp[i - x]
			if y <= i:
				dp[i] = max(dp[i], dp[i - y])
			if z <= i:
				dp[i] = max(dp[i - z], dp[i])
			if dp[i] != -1:
				dp[i] = dp[i] + 1
		if dp[n] == -1:
			return 0
		return dp[n]


class Solution:

	def solve(self, n, x, y, z):
		if n == 0:
			return 0
		if n < 0:
			return -999999
		if n >= x:
			xa = 1 + self.solve(n - x, x, y, z)
		if n >= y:
			ya = 1 + self.solve(n - y, x, y, z)
		if n >= z:
			za = 1 + self.solve(n - z, x, y, z)
		return max(xa, max(ya, za))

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			if i - x >= 0 and dp[i - x] != -1:
				dp[i] = max(dp[i], dp[i - x] + 1)
			if i - y >= 0 and dp[i - y] != -1:
				dp[i] = max(dp[i], dp[i - y] + 1)
			if i - z >= 0 and dp[i - z] != -1:
				dp[i] = max(dp[i], dp[i - z] + 1)
		if dp[n] == -1:
			return 0
		else:
			return dp[n]


import sys
sys.setrecursionlimit(10010)

class Solution:

	def getVal(self, dp, val, x, y, z):
		if dp[val] != -100000:
			return dp[val]
		if val - x >= 0:
			dp[val] = max(dp[val], self.getVal(dp, val - x, x, y, z) + 1)
		if val - y >= 0:
			dp[val] = max(dp[val], self.getVal(dp, val - y, x, y, z) + 1)
		if val - z >= 0:
			dp[val] = max(dp[val], self.getVal(dp, val - z, x, y, z) + 1)
		return dp[val]

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-100000] * (n + 1)
		dp[0] = 0
		self.getVal(dp, n, x, y, z)
		return max(0, dp[-1])


import sys

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			cutx = cuty = cutz = -999999999
			if i - x >= 0:
				cutx = 1 + dp[i - x]
			if i - y >= 0:
				cuty = 1 + dp[i - y]
			if i - z >= 0:
				cutz = 1 + dp[i - z]
			dp[i] = max(cutx, cuty, cutz)
		if dp[n] >= 0:
			return dp[n]
		else:
			return 0


import sys

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		sys.setrecursionlimit(4000)
		dp = [-1] * (n + 1)

		def findsol(n, x, y, z):
			if n == 0:
				return 0
			if n < 0:
				return -999999999
			if dp[n] != -1:
				return dp[n]
			cutx = cuty = cutz = cut = -888888888
			if n >= x:
				if n % x == 0:
					cutx = n // x
				else:
					cutx = 1 + findsol(n - x, x, y, z)
			if n >= y:
				if n % y == 0:
					cuty = n // y
				else:
					cuty = 1 + findsol(n - y, x, y, z)
			if n >= z:
				if n % z == 0:
					cutz = n // z
				else:
					cutz = 1 + findsol(n - z, x, y, z)
			cut = max(cutx, cuty, cutz)
			dp[n] = cut
			return cut
		val = findsol(n, x, y, z)
		return val if val >= 0 else 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			a1 = dp[i - x] if i - x >= 0 else -10000000000.0
			a2 = dp[i - y] if i - y >= 0 else -10000000000.0
			a3 = dp[i - z] if i - z >= 0 else -10000000000.0
			dp[i] = max(a1, a2, a3) + 1
		return dp[n] if dp[n] > 0 else 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0] * (n + 1)
		s = {x, y, z}
		arr = list(set(s))
		arr.sort()
		for a in arr:
			if a <= n:
				dp[a] = 1
		for i in range(1, n + 1):
			mxm = 0
			for l in arr:
				if i > l and dp[i - l]:
					mxm = max(mxm, dp[i - l] + 1)
			dp[i] = max(dp[i], mxm)
		return dp[-1]


class Solution:

	def maximizeTheCuts(self, l, p, q, r):
		dp = [-1] * (l + 1)
		dp[0] = 0
		for i in range(l + 1):
			if dp[i] == -1:
				continue
			if i + p <= l:
				dp[i + p] = max(dp[i + p], dp[i] + 1)
			if i + q <= l:
				dp[i + q] = max(dp[i + q], dp[i] + 1)
			if i + r <= l:
				dp[i + r] = max(dp[i + r], dp[i] + 1)
		if dp[l] == -1:
			dp[l] = 0
		return dp[l]


int_min = -10 ** 32

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [int_min for _ in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			if i - x >= 0:
				dp[i] = max(dp[i], dp[i - x] + 1)
			if i - y >= 0:
				dp[i] = max(dp[i], dp[i - y] + 1)
			if i - z >= 0:
				dp[i] = max(dp[i], dp[i - z] + 1)
		if dp[n] < 0:
			return 0
		else:
			return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):

		def manu(n, x, y, z):
			for i in range(1, n + 1):
				(s1, s2, s3) = (-10 ** 9, -10 ** 9, -10 ** 9)
				if i >= x:
					s1 = 1 + dp[i - x]
				if i >= y:
					s2 = 1 + dp[i - y]
				if i >= z:
					s3 = 1 + dp[i - z]
				dp[i] = max(s1, max(s2, s3))
			return dp[n]
		dp = [0 for i in range(n + 1)]
		f = manu(n, x, y, z)
		if f < 0:
			return 0
		return f


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		l = [x, y, z]
		dp = [-1 for i in range(n + 1)]
		dp[0] = 0
		for i in range(3):
			for j in range(1, n + 1):
				if j - l[i] >= 0 and dp[j - l[i]] != -1:
					dp[j] = max(dp[j], 1 + dp[j - l[i]])
		if dp[n] == -1:
			return 0
		return dp[n]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]

		def recursive(n):
			nonlocal dp, x, y, z
			if n == 0:
				return 0
			if dp[n] != -1:
				return dp[n]
			a = -float('inf')
			(b, c) = (a, a)
			if n >= x:
				a = 1 + recursive(n - x)
			if n >= y:
				b = 1 + recursive(n - y)
			if n >= z:
				c = 1 + recursive(n - z)
			dp[n] = max(a, max(b, c))
			return dp[n]
		a = recursive(n)
		if a == -float('inf'):
			return 0
		return a


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			(x1, y1, z1) = (0, 0, 0)
			if i >= x and dp[i - x] != 0:
				x1 = 1 + dp[i - x]
			if i >= y and dp[i - y] != 0:
				y1 = 1 + dp[i - y]
			if i >= z and dp[i - z] != 0:
				z1 = 1 + dp[i - z]
			dp[i] = max(x1, y1, z1)
		if dp[n] == 0:
			return 0
		return dp[n] - 1


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		if n < 0:
			return -1
		if n == 0:
			return 0
		dp = [None for i in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			dp[i] = -1
			f = dp[i - x] if i - x >= 0 else -1
			s = dp[i - y] if i - y >= 0 else -1
			t = dp[i - z] if i - z >= 0 else -1
			dp[i] = max(f, s, t)
			dp[i] = dp[i] if dp[i] == -1 else 1 + dp[i]
		return dp[i] if dp[i] > 0 else 0


import math

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		res = [-math.inf] * (n + 1)
		res[0] = 0
		for i in range(1, n + 1):
			if i - x >= 0:
				res[i] = max(res[i], res[i - x])
			if i - y >= 0:
				res[i] = max(res[i], res[i - y])
			if i - z >= 0:
				res[i] = max(res[i], res[i - z])
			if res[i] != -math.inf:
				res[i] += 1
		return res[n] if res[n] > 0 else 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		arr = [x, y, z]
		dp = [[-1 for _ in range(n + 1)] for _ in range(3)]
		dp[0][0] = 0
		for i in range(arr[0], n + 1):
			if dp[0][i - arr[0]] != -1:
				dp[0][i] = 1 + dp[0][i - arr[0]]
		for i in range(1, 3):
			for j in range(n + 1):
				if j == 0:
					dp[i][j] = 0
				elif j < arr[i] or dp[i][j - arr[i]] == -1:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = max(dp[i - 1][j], 1 + dp[i][j - arr[i]])
		if dp[-1][-1] == -1:
			return 0
		return dp[-1][-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]
		ans = backtrack(n, x, y, z, dp)
		if ans < 0:
			return 0
		return ans

def backtrack(n, x, y, z, dp):
	if n <= 0:
		return 0
	if dp[n] != -1:
		return dp[n]
	fi = -1000000009
	si = -1000000009
	li = -1000000009
	if n >= x:
		fi = backtrack(n - x, x, y, z, dp)
	if n >= y:
		si = backtrack(n - y, x, y, z, dp)
	if n >= z:
		li = backtrack(n - z, x, y, z, dp)
	dp[n] = 1 + max(fi, max(si, li))
	return dp[n]


import sys

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		t = [-1 for i in range(n + 1)]
		t[0] = 0
		for i in range(1, n + 1):
			if x <= i and t[i - x] != -1:
				t[i] = max(t[i], t[i - x] + 1)
			if y <= i and t[i - y] != -1:
				t[i] = max(t[i], t[i - y] + 1)
			if z <= i and t[i - z] != -1:
				t[i] = max(t[i], t[i - z] + 1)
		if t[n] == -1:
			return 0
		return t[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [float('-inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			maxc = float('-inf')
			for l in [x, y, z]:
				if i >= l:
					maxc = max(maxc, 1 + dp[i - l])
			dp[i] = maxc
		return max(dp[-1], 0)


class Solution:

	def maximizeTheCuts(self, N, x, y, z):
		dp = [float('-inf')] * (N + 1)
		dp[0] = 0
		for i in range(1, N + 1):
			if i - x >= 0:
				dp[i] = max(dp[i], dp[i - x] + 1)
			if i - y >= 0:
				dp[i] = max(dp[i], dp[i - y] + 1)
			if i - z >= 0:
				dp[i] = max(dp[i], dp[i - z] + 1)
		if dp[N] < 0:
			return 0
		return dp[N]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):

		def tab(n, x, y, z):
			memo = [0 for i in range(n + 1)]
			for i in range(1, n + 1):
				ans1 = -1
				ans2 = -1
				ans3 = -1
				if i - x >= 0:
					ans1 = memo[i - x]
				if i - y >= 0:
					ans2 = memo[i - y]
				if i - z >= 0:
					ans3 = memo[i - z]
				totalAns = max([ans1, ans2, ans3])
				if totalAns < 0:
					memo[i] = -1
				else:
					memo[i] = totalAns + 1
			if memo[-1] == -1:
				return 0
			return memo[-1]
		return tab(n, x, y, z)


class Solution:

	def find(self, n, x, y, z, dp):
		if n == 0:
			return 0
		if n < 0:
			return -9999999999
		if dp[n] != -1:
			return dp[n]
		n1 = self.find(n - x, x, y, z, dp) + 1
		n2 = self.find(n - y, x, y, z, dp) + 1
		n3 = self.find(n - z, x, y, z, dp) + 1
		dp[n] = max(n1, max(n2, n3))
		return dp[n]

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-999999] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			if i - x >= 0:
				dp[i] = max(dp[i], dp[i - x] + 1)
			if i - y >= 0:
				dp[i] = max(dp[i], dp[i - y] + 1)
			if i - z >= 0:
				dp[i] = max(dp[i], dp[i - z] + 1)
		if dp[n] < 0:
			return 0
		return dp[n]


import math

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			(a, b, c) = (-math.inf, -math.inf, -math.inf)
			if i - x >= 0:
				a = dp[i - x] + 1
			if i - y >= 0:
				b = dp[i - y] + 1
			if i - z >= 0:
				c = dp[i - z] + 1
			dp[i] = max(a, b, c)
		if dp[-1] < 0:
			return 0
		return dp[-1]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		XYZ = [x, y, z]
		import math
		Ans = [-math.inf] * (n + 1)
		Ans[0] = 0
		for i in range(1, n + 1):
			for j in XYZ:
				if i - j >= 0:
					Ans[i] = max(Ans[i], 1 + Ans[i - j])
		if Ans[n] > 0:
			return Ans[n]
		else:
			return 0


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		a = [0] * (n + 1)
		for i in range(1, n + 1):
			if i >= x:
				if i == x or a[i - x] != 0:
					a[i] = max(a[i], 1 + a[i - x])
			if i >= y:
				if i == y or a[i - y] != 0:
					a[i] = max(a[i], 1 + a[i - y])
			if i >= z:
				if i - z == 0 or a[i - z] != 0:
					a[i] = max(a[i], 1 + a[i - z])
		return a[n]


dp = [-1 for i in range(10 ** 4 + 1)]
import sys
sys.setrecursionlimit(10 ** 4 + 4)

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		global dp
		a = self.maximizeTheCuts2(n, x, y, z)
		dp = [-1 for i in range(10 ** 4 + 1)]
		if a < 0:
			return 0
		return a

	def maximizeTheCuts2(self, n, x, y, z):
		global dp
		if dp[n] != -1:
			return dp[n]
		if n == 0:
			return 0
		max_ = -10002
		if n >= x:
			a = self.maximizeTheCuts2(n - x, x, y, z)
			max_ = max(a, max_)
		if n >= y:
			b = self.maximizeTheCuts2(n - y, x, y, z)
			max_ = max(b, max_)
		if n >= z:
			c = self.maximizeTheCuts2(n - z, x, y, z)
			max_ = max(c, max_)
		dp[n] = 1 + max_
		return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		if n == 0:
			return 0
		dp = [0] * (n + 1)
		nums = set([x, y, z])
		for i in range(min(nums), n + 1):
			for num in nums:
				if i == num:
					dp[i] = max(dp[i], 1)
				elif i > num and dp[i - num] > 0:
					dp[i] = max(dp[i], dp[i - num] + 1)
		return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1] * (n + 1)
		dp[0] = 0
		dp[n] = 0
		arr = []
		arr.append(x)
		arr.append(y)
		arr.append(z)
		for i in range(3):
			for j in range(arr[i], n + 1):
				if dp[j - arr[i]] != -1 and dp[j] <= dp[j - arr[i]]:
					dp[j] = dp[j - arr[i]] + 1
		return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]

		def solve(n, x, y, z, dp):
			if n == 0:
				return 0
			if n < 0:
				return float('-inf')
			if dp[n] != -1:
				return dp[n]
			a = float('-inf')
			b = float('-inf')
			c = float('-inf')
			if x <= n:
				a = solve(n - x, x, y, z, dp) + 1
			if y <= n:
				b = solve(n - y, x, y, z, dp) + 1
			if z <= n:
				c = solve(n - z, x, y, z, dp) + 1
			dp[n] = max(max(a, b), c)
			return dp[n]

		def solvetb(n, x, y, z):
			dp = [-1 for i in range(n + 1)]
			dp[0] = 0
			for i in range(1, n + 1):
				if i - x >= 0 and dp[i - x] != -1:
					dp[i] = max(dp[i], dp[i - x] + 1)
				if i - y >= 0 and dp[i - y] != -1:
					dp[i] = max(dp[i], dp[i - y] + 1)
				if i - z >= 0 and dp[i - z] != -1:
					dp[i] = max(dp[i], dp[i - z] + 1)
			if dp[n] < 0:
				return 0
			return dp[n]
		ans = solvetb(n, x, y, z)
		return ans


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			f1 = float('-inf')
			f2 = float('-inf')
			f3 = float('-inf')
			if i - x >= 0:
				f1 = dp[i - x]
			if i - y >= 0:
				f2 = dp[i - y]
			if i - z >= 0:
				f3 = dp[i - z]
			dp[i] = 1 + max(f1, f2, f3)
		if dp[n] == float('-inf'):
			return 0
		else:
			return dp[n]


import sys
sys.setrecursionlimit(1 << 30)

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [-1 for i in range(n + 1)]

		def recursion(n, x, y, z):
			if n == 0:
				return 0
			if n < 0:
				return -float('inf')
			if dp[n] != -1:
				return dp[n]
			dp[n] = 1 + max(recursion(n - x, x, y, z), recursion(n - y, x, y, z), recursion(n - z, x, y, z))
			return dp[n]
		ans = recursion(n, x, y, z)
		if ans == -float('inf'):
			return 0
		else:
			return ans


import sys
sys.setrecursionlimit(40000)

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		memo = [-1] * (n + 1)
		a = self.Max(n, x, y, z, memo)
		if a < 0:
			return 0
		return a

	def Max(self, n, x, y, z, memo):
		if n == 0:
			return 0
		if n < 0:
			return float('-inf')
		if memo[n] != -1:
			return memo[n]
		a = self.Max(n - x, x, y, z, memo) + 1
		b = self.Max(n - y, x, y, z, memo) + 1
		c = self.Max(n - z, x, y, z, memo) + 1
		ans = max(a, b, c)
		memo[n] = ans
		return ans


import sys

class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0] * (n + 1)
		dp[0] = 0
		l = [x, y, z]
		for i in range(1, n + 1):
			max_cuts = float('-inf')
			for j in [x, y, z]:
				if i - j >= 0:
					max_cuts = max(max_cuts, dp[i - j])
			dp[i] = max_cuts + 1
		if dp[n] < 0:
			return 0
		else:
			return dp[n]


class Solution:

	def maximizeTheCuts(self, n, x, y, z):
		dp = [0 for i in range(n + 1)]
		for i in range(1, len(dp)):
			max1 = -1
			if x <= i:
				rem = i - x
				if dp[rem] >= 0:
					val = 1 + dp[rem]
					if val > max1:
						max1 = val
			if y <= i:
				rem = i - y
				if dp[rem] >= 0:
					val = 1 + dp[rem]
					if val > max1:
						max1 = val
			if z <= i:
				rem = i - z
				if dp[rem] >= 0:
					val = 1 + dp[rem]
					if val > max1:
						max1 = val
			dp[i] = max1
		if dp[len(dp) - 1] == -1:
			return 0
		else:
			return dp[len(dp) - 1]