There is a group of G members, and a list of various crimes they could commit.
The ith crime generates a profit[i] and requires group[i] members to participate in it.
If a member participates in one crime, that member can't participate in another crime.
Let's call a profitable scheme any subset of these crimes that generates at least P profit, and the total number of members participating in that subset of crimes is at most G.
How many schemes can be chosen?  Since the answer may be very large, return it modulo 10^9 + 7.
 
Example 1:
Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: 
To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.


Example 2:
Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: 
To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

 

Note:

1 <= G <= 100
0 <= P <= 100
1 <= group[i] <= 100
0 <= profit[i] <= 100
1 <= group.length = profit.length <= 100

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        

Solutions:
class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7
		(group_len, profit_len) = (len(group), len(profit))
		dp = [[0] * (G + 1) for _ in range(P + 1)]
		dp[0][0] = 1
		for (pro, gro) in zip(profit, group):
			dp2 = [x[:] for x in dp]
			for p1 in range(P + 1):
				p = min(pro + p1, P)
				for g1 in range(G + 1 - gro):
					g = g1 + gro
					dp2[p][g] += dp[p1][g1]
					dp2[p][g] %= MOD
			dp = dp2
		return sum(dp[-1]) % MOD


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7
		cur = [[0] * (G + 1) for _ in range(P + 1)]
		cur[0][0] = 1
		for (p0, g0) in zip(profit, group):
			cur2 = [row[:] for row in cur]
			for p1 in range(P + 1):
				p2 = min(p1 + p0, P)
				for g1 in range(G - g0 + 1):
					g2 = g1 + g0
					cur2[p2][g2] += cur[p1][g1]
					cur2[p2][g2] %= MOD
			cur = cur2
		return sum(cur[-1]) % MOD


class Solution:

	def profitableSchemes(self, G, P, group, profit):
		dp = [[0] * (G + 1) for i in range(P + 1)]
		dp[0][0] = 1
		for (p, g) in zip(profit, group):
			for i in range(P, -1, -1):
				for j in range(G - g, -1, -1):
					dp[min(i + p, P)][j + g] += dp[i][j]
		return sum(dp[P]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		memo = [[0] * (G + 1) for _ in range(P + 1)]
		memo[0][0] = 1
		for (p, g) in zip(profit, group):
			for i in reversed(range(P + 1)):
				for j in reversed(range(G + 1 - g)):
					memo[min(i + p, P)][j + g] += memo[i][j]
		return sum(memo[-1]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = 10 ** 9 + 7
		n = len(group)
		dp = [[0] * (G + 1) for _ in range(P + 1)]
		dp[0][0] = 1
		for (g, p) in zip(group, profit):
			for i in range(P, -1, -1):
				for j in range(G - g, -1, -1):
					dp[min(i + p, P)][j + g] += dp[i][j]
		return sum(dp[-1]) % mod


class Solution:

	def profitableSchemes(self, G, P, group, profit):
		dp = [[0] * (G + 1) for i in range(P + 1)]
		dp[0][0] = 1
		for (p_gained, g_needed) in zip(profit, group):
			ndp = [[0] * (G + 1) for i in range(P + 1)]
			for p in range(P + 1):
				for g in range(0, G + 1):
					ndp[p][g] += dp[p][g]
					if g >= g_needed:
						ndp[p][g] += dp[max(p - p_gained, 0)][g - g_needed]
			dp = ndp
		return sum(dp[P]) % (10 ** 9 + 7)

	def profitableSchemes(self, G, P, group, profit):
		dp = [[0] * (G + 1) for i in range(P + 1)]
		dp[0][0] = 1
		for (p_gained, g_needed) in zip(profit, group):
			for p in range(P, -1, -1):
				for g in range(G, g_needed - 1, -1):
					dp[p][g] += dp[max(p - p_gained, 0)][g - g_needed]
		return sum(dp[P]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		dp = [[0] * (G + 1) for _ in range(P + 1)]
		dp[0][0] = 1
		for (p, g) in zip(profit, group):
			for i in range(P, -1, -1):
				for j in range(G - g, -1, -1):
					if i + p >= P:
						dp[P][j + g] += dp[i][j]
					else:
						dp[i + p][j + g] += dp[i][j]
		return sum(dp[P]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		m = 10 ** 9 + 7
		cur = [[0] * (G + 1) for _ in range(P + 1)]
		cur[0][0] = 1
		for (p0, g0) in zip(profit, group):
			for p1 in range(P, -1, -1):
				for g1 in range(G, g0 - 1, -1):
					cur[p1][g1] += cur[max(0, p1 - p0)][g1 - g0]
		return sum(cur[-1]) % m


class Solution(object):

	def profitableSchemes(self, G, P, group, profit):
		mod = 10 ** 9 + 7
		dp = [[0 for _ in range(G + 1)] for _ in range(P + 1)]
		dp[0][0] = 1
		for (g, p) in zip(group, profit):
			cur = [row[:] for row in dp]
			for g_pre in range(G - g + 1):
				for p_pre in range(P + 1):
					p_now = min(P, p_pre + p)
					cur[p_now][g_pre + g] += dp[p_pre][g_pre]
			dp = cur
		return sum(dp[-1]) % mod


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		M = pow(10, 9) + 7
		dp = [[0] * (P + 1) for _ in range(G + 1)]
		dp[0][0] = 1
		for k in range(len(group)):
			gro = group[k]
			pro = profit[k]
			for i in range(G - gro, -1, -1):
				for j in range(P, -1, -1):
					g = i + gro
					p = min(P, j + pro)
					dp[g][p] += dp[i][j]
		res = 0
		for i in range(G + 1):
			res += dp[i][P]
		return res % M


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		C = len(profit)
		dp = [[[0] * (C + 1) for _ in range(P + 1)] for _ in range(G + 1)]
		for g in range(G + 1):
			dp[g][0][0] = 1
		for g in range(0, G + 1):
			for p in range(0, P + 1):
				for (c, [hand_needed, p_gained]) in enumerate(zip(group, profit), 1):
					dp[g][p][c] = dp[g][p][c - 1]
					if hand_needed <= g:
						prev_at_least = max(0, p - p_gained)
						dp[g][p][c] += dp[g - hand_needed][prev_at_least][c - 1]
					dp[g][p][c] = dp[g][p][c] % 1000000007
		return dp[G][P][-1] % 1000000007

	def profitableSchemes(self, G, P, group, profit):
		dp = [[0] * (G + 1) for i in range(P + 1)]
		dp[0][0] = 1
		for (p, g) in zip(profit, group):
			for i in range(P, -1, -1):
				for j in range(G - g, -1, -1):
					dp[min(i + p, P)][j + g] += dp[i][j]
		return sum(dp[P]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7
		dp = [[0] * (P + 1) for i in range(G + 1)]
		for i in range(G + 1):
			dp[i][0] = 1
		for (g, p) in zip(group, profit):
			dp2 = [row[:] for row in dp]
			for g1 in range(g, G + 1):
				for p1 in range(P + 1):
					dp2[g1][p1] = (dp2[g1][p1] + dp[g1 - g][max(0, p1 - p)]) % MOD
			dp = dp2
		return dp[G][P]


from functools import lru_cache

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		C = len(group)
		MOD = pow(10, 9) + 7
		dp = [[0] * (P + 1) for _ in range(G + 1)]
		dp[0][0] = 1
		for c in range(1, C + 1):
			g = group[c - 1]
			p = profit[c - 1]
			for i in range(G, g - 1, -1):
				for j in range(P, -1, -1):
					dp[i][j] = (dp[i][j] + dp[i - g][max(0, j - p)]) % MOD
		return sum((dp[i][P] for i in range(G + 1))) % MOD


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		(n, M) = (len(group), 10 ** 9 + 7)
		dp = [[0] * (P + 1) for _ in range(G + 1)]
		dp[0][0] = 1
		for k in range(1, n + 1):
			(g, p) = (group[k - 1], profit[k - 1])
			for i in range(G, g - 1, -1):
				for j in range(P, -1, -1):
					dp[i][j] = (dp[i][j] + dp[i - g][max(0, j - p)]) % M
		res = 0
		for i in range(G + 1):
			res = (res + dp[i][P]) % M
		return res


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		count_dict = {}
		base = int(1000000000.0 + 7)
		for (groupi, profiti) in zip(group, profit):
			if groupi > G or groupi <= 0:
				continue
			tmp_dict = count_dict.copy()
			for ((groupj, profitj), count) in tmp_dict.items():
				if groupj + groupi <= G:
					if profiti + profitj >= P:
						count_dict[groupi + groupj, P] = count_dict.get((groupi + groupj, P), 0) + count % base
					else:
						count_dict[groupi + groupj, profiti + profitj] = count_dict.get((groupi + groupj, profiti + profitj), 0) + count % base
			if profiti >= P:
				count_dict[groupi, P] = count_dict.get((groupi, P), 0) + 1
			else:
				count_dict[groupi, profiti] = count_dict.get((groupi, profiti), 0) + 1
		out = 0
		for ((groupi, profiti), count) in count_dict.items():
			if profiti >= P:
				out += count
		return out % base


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		m = 10 ** 9 + 7
		table = [[0] * (G + 1) for _ in range(P + 1)]
		table[0][0] = 1
		for (g, p) in zip(group, profit):
			for pi in range(P, -1, -1):
				for gi in range(G - g, -1, -1):
					new_pi = min(P, pi + p)
					table[new_pi][gi + g] = (table[new_pi][gi + g] + table[pi][gi]) % m
		total = 0
		for x in table[P]:
			total = (total + x) % m
		return total


mod_ = 10 ** 9 + 7

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		axis_group = G + 1
		axis_profit = P + 1
		n_profit = len(profit)
		mat = [[0 for p in range(axis_profit)] for g in range(axis_group)]
		mat[0][0] = 1
		for (pos, cur_profit) in enumerate(profit):
			cur_people = group[pos]
			for g in range(axis_group - 1, cur_people - 1, -1):
				for p in range(cur_profit + axis_profit - 1, cur_profit - 1, -1):
					p2 = min(axis_profit - 1, p)
					mat[g][p2] = (mat[g][p2] + mat[g - cur_people][p - cur_profit]) % mod_
		count = 0
		for row in mat:
			count = (count + sum(row[P:])) % mod_
		return count


MOD = int(10 ** 9 + 7)

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		n = len(group)
		dp = 128 * 101 * [0]
		dp[0] = 1
		for (g, p) in zip(group, profit):
			old = dp.copy()
			for h in range(0, G - g + 1):
				for q in range(P + 1):
					x = h + g << 7 | min(p + q, P)
					y = dp[x]
					y += old[h << 7 | q]
					if y > MOD:
						y -= MOD
					dp[x] = y
		return sum((dp[g << 7 | P] for g in range(G + 1))) % MOD


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = 10 ** 9 + 7
		dp = [[0] * (G + 1) for _ in range(P + 1)]
		dp[0][0] = 1
		for (g0, p0) in zip(group, profit):
			dp2 = [row[:] for row in dp]
			for p1 in range(P + 1):
				p2 = min(P, p1 + p0)
				for g1 in range(G - g0 + 1):
					g2 = g1 + g0
					dp2[p2][g2] += dp[p1][g1]
					dp2[p2][g2] %= mod
			dp = dp2
		return sum(dp[-1]) % mod


class Solution:

	def profitableSchemes(self, G: int, P: int, groups: List[int], profits: List[int]) -> int:
		dp = [[0] * (P + 1) for i in range(0, G + 1)]
		for i in range(0, G + 1):
			dp[i][0] = 1
		N = len(groups)
		l = []
		for i in range(0, N):
			l.append((groups[i], profits[i]))
		l.sort()
		for i in range(0, N):
			(group, profit) = l[i]
			if group > G:
				break
			for j in range(G, group - 1, -1):
				gremain = j - group
				for k in range(P, -1, -1):
					dp[j][k] += dp[gremain][max(k - profit, 0)]
					dp[j][k] %= 10 ** 9 + 7
		return dp[G][P]


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = 10 ** 9 + 7
		K = len(group)
		dp = [[[0] * (G + 1) for _ in range(P + 1)] for _ in range(K + 1)]
		dp[0][0][0] = 1
		for k in range(1, K + 1):
			p = profit[k - 1]
			g = group[k - 1]
			for i in range(P + 1):
				for j in range(G + 1):
					dp[k][i][j] = dp[k - 1][i][j]
					if j >= g:
						dp[k][i][j] += dp[k - 1][max(0, i - p)][j - g]
		return sum(dp[K][P]) % mod


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		gp = list(zip(group, profit))
		dp = defaultdict(int)
		dp[G, P] = 1
		while gp:
			(g, p) = gp.pop()
			for ((g0, p0), count) in list(dp.items()):
				if g0 >= g:
					prof_left = max(0, p0 - p)
					dp[g0 - g, prof_left] += count
		return sum([count for ((g, p), count) in list(dp.items()) if p == 0]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		Mod = 10 ** 9 + 7
		l = len(group)
		f = [[[0] * (G + 1) for i in range(P + 1)] for j in range(2)]
		f[1][0][0] = 1
		for i in range(l):
			f[i % 2] = [j[:] for j in f[(i - 1) % 2]]
			for p in range(P + 1):
				for g in range(G + 1 - group[i]):
					mp = min(P, profit[i] + p)
					(a, b) = (i % 2, (i - 1) % 2)
					if g + group[i] <= G:
						f[a][mp][g + group[i]] = (f[a][mp][g + group[i]] + f[b][p][g]) % Mod
		return sum(f[(l - 1) % 2][-1]) % Mod
		Syn = sorted([(profit[i], group[i]) for i in range(l)])
		(s, pre) = (0, [])
		for p in Syn:
			s += p[0]
			pre.append(s)
		Memo = {}

		def dfs(g, p, i):
			if (g, p, i) in Memo:
				return Memo[g, p, i]
			if i == 0:
				if p <= 0:
					Memo[g, p, i] = 1
					if g >= Syn[i][1]:
						Memo[g, p, i] += 1
				elif p > Syn[i][0]:
					Memo[g, p, i] = 0
				elif g >= Syn[i][1]:
					Memo[g, p, i] = 1
				else:
					Memo[g, p, i] = 0
				return Memo[g, p, i]
			if p > pre[i]:
				Memo[g, p, i] = 0
				return 0
			if g == 0 and p <= 0:
				Memo[g, p, i] = 1
				return 1
			if g - Syn[i][1] < 0:
				r = dfs(g, p, i - 1)
			else:
				tmp = p - Syn[i][0] if p - Syn[i][0] >= 0 else 0
				r = (dfs(g - Syn[i][1], p - Syn[i][0], i - 1) + dfs(g, p, i - 1)) % Mod
			Memo[g, p, i] = r
			return r
		dfs(G, P, l - 1)
		return Memo[G, P, l - 1]


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = 10 ** 9 + 7
		DP = [[[0] * (P + 1) for _ in range(G + 1)] for _ in range(len(group) + 1)]
		DP[0][0][0] = 1
		for k in range(1, len(group) + 1):
			g = group[k - 1]
			p = profit[k - 1]
			for i in range(G + 1):
				for j in range(P + 1):
					DP[k][i][j] = DP[k - 1][i][j]
					if i - g < 0:
						continue
					DP[k][i][j] = DP[k - 1][i][j] + DP[k - 1][i - g][max(0, j - p)]
		ans = 0
		for i in range(G + 1):
			ans += DP[len(group)][i][P] % mod
		return ans % mod


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7
		Cnt = 0
		dp_ = [[0] * (G + 1) for _ in range(P + 1)]
		dp_[0][0] = 1
		for i in range(1, len(group) + 1):
			for p in range(P, -1, -1):
				for v in range(G - group[i - 1], -1, -1):
					dp_[min(p + profit[i - 1], P)][v + group[i - 1]] = (dp_[p][v] + dp_[min(p + profit[i - 1], P)][v + group[i - 1]]) % MOD
		return sum(dp_[P]) % MOD


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		n = len(profit)
		dp = [[[0 for g in range(G + 1)] for p in range(P + 1)] for i in range(1 + n)]
		dp[0][0][0] = 1
		for i in range(1, n + 1):
			for p in range(P + 1):
				for g in range(G + 1):
					dp[i][p][g] = dp[i - 1][p][g]
					if g >= group[i - 1]:
						dp[i][p][g] += dp[i - 1][max(p - profit[i - 1], 0)][g - group[i - 1]]
		result = 0
		for value in dp[n][P][:G + 1]:
			result += value
		return result % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		M = 10 ** 9 + 7
		dp = [[[0 for j in range(G + 1)] for i in range(P + 1)] for k in range(len(group) + 1)]
		dp[0][0][0] = 1
		for k in range(1, len(group) + 1):
			for i in range(P + 1):
				for j in range(G + 1):
					dp[k][i][j] = dp[k - 1][i][j]
					if j >= group[k - 1]:
						dp[k][i][j] += dp[k - 1][max(0, i - profit[k - 1])][j - group[k - 1]]
		return sum(dp[len(group)][P]) % M


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		dp = [[[0 for _ in range(G + 1)] for _ in range(P + 1)] for _ in range(len(group) + 1)]
		dp[0][0][0] = 1
		for i in range(1, len(group) + 1):
			for p in range(P + 1):
				for g in range(G + 1):
					dp[i][p][g] += dp[i - 1][p][g]
					if g + group[i - 1] < G + 1:
						dp[i][min(p + profit[i - 1], P)][g + group[i - 1]] += dp[i - 1][p][g]
		return sum([dp[len(group)][P][g] for g in range(1, G + 1)]) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		dp = [[[0 for _ in range(P + 1)] for _ in range(G + 1)] for _ in range(len(profit) + 1)]
		dp[0][-1][-1] = 1
		mod = int(1000000000.0 + 7)
		for i in range(1, len(profit) + 1):
			for j in range(G, -1, -1):
				for k in range(P, -1, -1):
					dp[i][j][k] = dp[i - 1][j][k]
				for k in range(P, -1, -1):
					if j + group[i - 1] <= G:
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + group[i - 1]][min(k + profit[i - 1], P)]) % mod
		res = 0
		for j in range(G + 1):
			res = (res + dp[-1][j][0]) % mod
		return res


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		n = len(group)

		@lru_cache(None)
		def dfs(i, g, p):
			if g == 0:
				return 1 if p <= 0 else 0
			if i == n:
				return 1 if p <= 0 else 0
			ans = dfs(i + 1, g, p)
			if group[i] <= g:
				ans += dfs(i + 1, g - group[i], max(p - profit[i], 0))
			return ans % (10 ** 9 + 7)
		return dfs(0, G, P) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(i, g, p):
			if g < 0:
				return 0
			if i == n:
				return 1 if p == 0 else 0
			a = dp(i + 1, g - group[i], max(0, p - profit[i]))
			b = dp(i + 1, g, p)
			return (a + b) % MOD
		n = len(group)
		return dp(0, G, P)


from functools import lru_cache

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		@lru_cache(None)
		def sack(g, i, p):
			if i == len(profit) or g == 0:
				return p >= P
			ans = 0
			if group[i] <= g:
				ans = sack(g - group[i], i + 1, min(P, p + profit[i]))
			return ans + sack(g, i + 1, p)
		return sack(G, 0, 0) % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		@lru_cache(None)
		def dfs(index, curr_profit, members_left):
			if index == len(profit) or members_left == 0:
				return curr_profit == 0
			res = 0
			res += dfs(index + 1, curr_profit, members_left)
			if members_left - group[index] >= 0:
				res += dfs(index + 1, max(0, curr_profit - profit[index]), members_left - group[index])
			return res % (10 ** 9 + 7)
		return dfs(0, P, G)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = 10 ** 9 + 7
		m = len(group)

		@lru_cache(None)
		def dfs(i, g, p):
			if i == m:
				return int(p <= 0)
			res = 0
			if g - group[i] >= 0:
				res += dfs(i + 1, g - group[i], max(0, p - profit[i]))
			res += dfs(i + 1, g, p)
			return res
		return dfs(0, G, P) % mod


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		mod = int(10 ** 9) + 7
		N = len(group)
		dp = [[[None] * (G + 1) for _ in range(P + 1)] for _ in range(N + 1)]

		def solve(i, j, k):
			if k < 0:
				return 0
			if i == N:
				return 1 if j == 0 else 0
			if dp[i][j][k] is None:
				result = solve(i + 1, j, k) + solve(i + 1, max(j - profit[i], 0), k - group[i])
				dp[i][j][k] = result % mod
			return dp[i][j][k]
		return solve(0, P, G)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		@lru_cache(None)
		def recur(hc, mp, ind):
			if hc < 0:
				return 0
			if ind >= len(profit):
				if mp <= 0:
					return 1
				else:
					return 0
			take = recur(hc - group[ind], max(0, mp - profit[ind]), ind + 1)
			skip = recur(hc, mp, ind + 1)
			return (take + skip) % (10 ** 9 + 7)
		return recur(G, P, 0)


import functools

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		n = len(profit)

		@functools.lru_cache(None)
		def dp(g, p, i):
			if i == n or g == 0:
				if p == 0:
					return 1
				return 0
			ans = dp(g, p, i + 1) % (10 ** 9 + 7)
			if g - group[i] >= 0:
				ans += dp(g - group[i], max(0, p - profit[i]), i + 1)
				ans %= 10 ** 9 + 7
			return ans % (10 ** 9 + 7)
		return dp(G, P, 0) % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		MOD = 10 ** 9 + 7
		n = len(profit)
		psum = profit + [0]
		for i in range(n)[::-1]:
			psum[i] += psum[i + 1]

		@lru_cache(None)
		def dfs(g, p, idx):
			if g < 0:
				return 0
			if idx == n:
				return 1 if p <= 0 else 0
			p = max(p, 0)
			res = (dfs(g, p, idx + 1) + dfs(g - group[idx], p - profit[idx], idx + 1)) % MOD
			return res
		return dfs(G, P, 0)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		@lru_cache(None)
		def dp(i, total_profit, member_left):
			if i == len(profit):
				return 0
			take = 0
			if member_left >= group[i]:
				take += 1 if profit[i] + total_profit >= P else 0
				take += dp(i + 1, min(P, total_profit + profit[i]), max(0, member_left - group[i]))
			skip = dp(i + 1, total_profit, member_left)
			return take + skip
		return dp(0, 0, G) % (10 ** 9 + 7)


from collections import defaultdict

class Solution:
	MOD = 10 ** 9 + 7

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		remaining_profit = sum(profit)
		(schemes, next_schemes) = (defaultdict(int), defaultdict(int))
		schemes[0, 0] = 1
		for (i, p) in enumerate(profit):
			remaining_profit -= p
			for (curr_g, curr_p) in [(0, 0), (group[i], profit[i])]:
				for (prev_g, prev_p) in schemes:
					next_g = prev_g + curr_g
					next_p = min(prev_p + curr_p, P)
					if next_p + remaining_profit >= P and next_g <= G:
						next_schemes[next_g, next_p] += schemes[prev_g, prev_p]
			(schemes, next_schemes) = (next_schemes, defaultdict(int))
			for k in schemes:
				schemes[k] = schemes[k] % Solution.MOD
		return sum(schemes.values()) % Solution.MOD


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		@lru_cache(None)
		def dp(i, ppl_left, money):
			if ppl_left < 0:
				return 0
			if i == len(group):
				return 0
			ret = 0
			ret += dp(i + 1, ppl_left, money)
			if money + profit[i] >= P and ppl_left >= group[i]:
				ret += 1
			ret += dp(i + 1, ppl_left - group[i], min(money + profit[i], P))
			return ret % (10 ** 9 + 7)
		return dp(0, G, 0)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		profitDict = defaultdict(dict)
		profitList = [(g, p) for (g, p) in zip(group, profit)]
		profitList.sort()
		ans = 0
		for (g, p) in profitList:
			newProfitDict = defaultdict(dict)
			for p0 in list(profitDict.keys()):
				thisProfit = p0 + p
				for preG in list(profitDict[p0].keys()):
					thisG = preG + g
					if thisG > G:
						profitDict[p0].pop(preG)
					else:
						if thisProfit >= P:
							ans += profitDict[p0][preG]
						if thisG in newProfitDict[thisProfit]:
							newProfitDict[thisProfit][thisG] += profitDict[p0][preG]
						else:
							newProfitDict[thisProfit][thisG] = profitDict[p0][preG]
			for profitTemp in newProfitDict:
				for groupTemp in newProfitDict[profitTemp]:
					if groupTemp in profitDict[profitTemp]:
						profitDict[profitTemp][groupTemp] += newProfitDict[profitTemp][groupTemp]
					else:
						profitDict[profitTemp][groupTemp] = newProfitDict[profitTemp][groupTemp]
			if g <= G and p >= P:
				ans += 1
			if g in profitDict[p]:
				profitDict[p][g] += 1
			else:
				profitDict[p][g] = 1
		return ans % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		dp = [[[0 for _ in range(len(profit) + 1)] for _ in range(P + 1)] for _ in range(G + 1)]
		if P == 0:
			dp[1][0][0] = 1
		for i in range(1, G + 1):
			for j in range(0, P + 1):
				for k in range(1, len(profit) + 1):
					dp[i][j][k] = dp[i][j][k - 1]
					if profit[k - 1] >= j and i >= group[k - 1]:
						dp[i][j][k] += 1
					if i > group[k - 1]:
						remaining_g = i - group[k - 1]
						remaining_p = max(0, j - profit[k - 1])
						dp[i][j][k] += dp[remaining_g][remaining_p][k - 1]
					dp[i][j][k] %= 10 ** 9 + 7
		return dp[G][P][len(profit)]


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		BOUND = 10 ** 9 + 7
		dp = {}

		def f(g, p, i):
			if (g, p, i) in dp:
				return dp[g, p, i]
			if g == 0:
				return 0
			if i == 0:
				return 1 if group[0] <= g and profit[0] >= p else 0
			res = f(g, p, i - 1)
			if group[i] <= g:
				if profit[i] >= p:
					res += 1
				res += f(g - group[i], max(0, p - profit[i]), i - 1)
			dp[g, p, i] = res % BOUND
			return dp[g, p, i]
		return f(G, P, len(group) - 1)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:

		def helper(G, P, group, profit, scheme, memos):
			if scheme == len(group):
				if P <= 0 and G >= 0:
					return 1
				return 0
			if G < 0:
				return 0
			if P < 0:
				P = 0
			if P not in memos[G][scheme]:
				added = helper(G - group[scheme], P - profit[scheme], group, profit, scheme + 1, memos)
				not_added = helper(G, P, group, profit, scheme + 1, memos)
				memos[G][scheme][P if P > 0 else 0] = added + not_added
			return memos[G][scheme][P]
		memos = [[{} for _ in group] for _ in range(G + 1)]
		return helper(G, P, group, profit, 0, memos) % (10 ** 9 + 7)


class Solution:

	def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
		dp = {}
		return self.rec(group, profit, dp, 0, G, P) % (10 ** 9 + 7)

	def rec(self, grp, profit, dp, i, mem_left, pr):
		if i >= len(grp):
			if pr <= 0:
				return 1
			return 0
		pr = max(pr, 0)
		if (i, mem_left, pr) in dp:
			return dp[i, mem_left, pr]
		dp[i, mem_left, pr] = self.rec(grp, profit, dp, i + 1, mem_left, pr) % (10 ** 9 + 7)
		if grp[i] <= mem_left:
			dp[i, mem_left, pr] += self.rec(grp, profit, dp, i + 1, mem_left - grp[i], pr - profit[i]) % (10 ** 9 + 7)
		return dp[i, mem_left, pr]