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

Difficulty: interview

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):
            # p0, g0 : the current crime profit and group size
            cur2 = [row[:] for row in cur]
            for p1 in range(P + 1):
                # p1 : the current profit
                # p2 : the new profit after committing this crime
                p2 = min(p1 + p0, P)
                for g1 in range(G - g0 + 1):
                    # g1 : the current group size
                    # g2 : the new group size after committing this crime
                    g2 = g1 + g0
                    cur2[p2][g2] += cur[p1][g1]
                    cur2[p2][g2] %= MOD
            cur = cur2
        # Sum all schemes with profit P and group size 0 <= g <= G.
        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)
    # def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
    #     schemes=[(pro, kitnelog) for pro, kitnelog in zip(profit, group)]
    #     nonlocal dump
    #     dump={}
    #     nonlocal dump1
    #     dump1={}
    #     return self.getans(G, P, schemes)
    # def getans(self, g, p, schemes, mod=(10**9+7)):
    #     nonlocal dump
    #     nonlocal dump1
    #     if len(schemes)==0:
    #         if p<=0:
    #             return 1
    #         return 0
    #     if g<=0 and p>0:
    #         return 0
    #     if p<=0:
    #         return self.numsubsetslessthan(g, schemes)
    #     if (g, p, len(schemes)) in dump:
    #         return dump[(g, p, len(schemes))]
    #     a=self.getans(g-schemes[-1][1], p-schemes[-1][0], schemes[:-1]) if g>=schemes[-1][1] else 0
    #     b=self.getans(g, p, schemes[:-1])
    #     dump[(g, p, len(schemes))]=(a+b)%mod
    #     return dump[(g, p, len(schemes))]
    # def numsubsetslessthan(self, g, schemes, mod=10**9+7):
    #     nonlocal dump1
    #     if len(schemes)==0:
    #         return 1
    #     if (g, len(schemes)) in dump1:
    #         return dump1[(g, len(schemes))]
    #     a=self.numsubsetslessthan(g-schemes[-1][1], schemes[:-1]) if g>=schemes[-1][1] else 0
    #     b=self.numsubsetslessthan(g, schemes[:-1])
    #     dump1[(g, len(schemes))]=(a+b)%mod
    #     return dump1[(g, len(schemes))]


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:
        memo =[[0]*(G+1) for _ in range(P+1)]
        memo[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):
                    memo[min(P,p+i)][j+g] += memo[i][j]
        return sum(memo[P])%(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
        
        
        
        # n = len(group)
        # dp = [[0, 0]]
        # ans = 0
        # for i, (g, p) in enumerate(zip(group, profit)):
        #     dp2 = []
        #     for pro, num in dp:
        #         if num + g <= G and pro + p < P:
        #             dp2.append([pro + p, num + g])
        #         elif num + g <= G and pro + p >= P:
        #             rem = G - num - g
        #             ans += 2 ** (n - i - 1)
        #     dp += dp2
        # return ans % mod


class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        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:
        dp = [[0]*(G+1) for _ in range(P+1)]
        
        dp[0][0] = 1
        # for i in range(G+1):
        #     dp[0][i] = 1
        
        for i in range(len(profit)):
            p = profit[i]
            g = group[i]
            for i in range(P, -1, -1):
                for j in range(G-g, -1, -1):
                    dp[min(P, i + p)][j+g] += dp[i][j]
                    
        return sum(dp[-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
        # Key point is to iterate reversely, like knapsack problem
        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] = [1] * (G + 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, P, group, profit):
        dp = [[0] * (G + 1) for i in range(P + 1)]
        dp[0][0] = 1
        for p, g in zip(profit, group):
            dp2=[i[:] for i in dp]
            for i in range(P, -1, -1):
                for j in range(G - g, -1, -1):
                    dp2[min(i + p, P)][j + g] += dp[i][j]
            dp=dp2
        return sum(dp[P]) % (10**9 + 7)
    # def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
    #     schemes=[(pro, kitnelog) for pro, kitnelog in zip(profit, group)]
    #     nonlocal dump
    #     dump={}
    #     nonlocal dump1
    #     dump1={}
    #     return self.getans(G, P, schemes)
    # def getans(self, g, p, schemes, mod=(10**9+7)):
    #     nonlocal dump
    #     nonlocal dump1
    #     if len(schemes)==0:
    #         if p<=0:
    #             return 1
    #         return 0
    #     if g<=0 and p>0:
    #         return 0
    #     if p<=0:
    #         return self.numsubsetslessthan(g, schemes)
    #     if (g, p, len(schemes)) in dump:
    #         return dump[(g, p, len(schemes))]
    #     a=self.getans(g-schemes[-1][1], p-schemes[-1][0], schemes[:-1]) if g>=schemes[-1][1] else 0
    #     b=self.getans(g, p, schemes[:-1])
    #     dump[(g, p, len(schemes))]=(a+b)%mod
    #     return dump[(g, p, len(schemes))]
    # def numsubsetslessthan(self, g, schemes, mod=10**9+7):
    #     nonlocal dump1
    #     if len(schemes)==0:
    #         return 1
    #     if (g, len(schemes)) in dump1:
    #         return dump1[(g, len(schemes))]
    #     a=self.numsubsetslessthan(g-schemes[-1][1], schemes[:-1]) if g>=schemes[-1][1] else 0
    #     b=self.numsubsetslessthan(g, schemes[:-1])
    #     dump1[(g, len(schemes))]=(a+b)%mod
    #     return dump1[(g, len(schemes))]


class Solution:
    def profitableSchemes(self,G, P, group, profit):
        dp = [[1]+[0]*G] + [[0]*(G+1) for _ in range(P)]
        for p, g in zip(profit, group):
            for i in range(P,-1,-1):
                for j in range(G-g,-1,-1):
                    dp[min(P,i+p)][g+j] += 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:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        # Dynamic Programming
        # Time  complexity: O(N x P x G), where N is the number of crimes available to the gang.
        # Space complexity: O(P x G)
        # 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


        MOD = 10**9 + 7
        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):
                    dp[min(P, i + p)][g + j] += dp[i][j]

        return sum(dp[P]) % MOD


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:
        # knapsack dp
        # dp[g][p]= n means we have n combinations for we used g people left and made p profit
        
        dp = [[0]*(P+1) for i in range(G+1)]
        dp[0][0] = 1
        
        for g,p in zip(group,profit):
            for i in range(G-g,-1,-1):
                for j in range(P,-1,-1):
                    dp[i+g][min(j+p,P)]+=dp[i][j]
            #print(dp)
        res = 0
        for i in range(G+1):
            res+=dp[i][-1]
        return res%(10**9+7)
                    


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:
        
        # dp[g][p][c], ways for consider c_th crime, with g gangs to achieve profit p
        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)
    '''
    
    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:
        M = 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] %= M
            cur = cur2
        return sum(cur[-1])%M

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
        
        # @lru_cache(None)
        # def dp(c, p, g):
        #     if c == 0:
        #         return 1 if p == 0 else 0
        #     result = dp(c-1, p, g)
        #     if g >= group[c-1]:
        #         result += dp(c-1, max(0, p-profit[c-1]), g-group[c-1])
        #     result %= MOD
        #     return result
        # return dp(C, P, G)
    
        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):
                    #print(i, j, i-g, max(0, j-p))
                    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[i][j] is the # of schemes of i people and j profit
        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

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
        
        # @lru_cache(None)
        # def dp(c, p, g):
        #     if c == 0:
        #         return 1 if p == 0 else 0
        #     result = dp(c-1, p, g)
        #     if g >= group[c-1]:
        #         result += dp(c-1, max(0, p-profit[c-1]), g-group[c-1])
        #     result %= MOD
        #     return result
        # return dp(C, P, G)
    
        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):
                    #print(i, j, i-g, max(0, j-p))
                    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:
        count_dict = {}
        base = int(1e9 + 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
        # table[p][g] to index
        
        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


class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        
        
        dp = [[0] * (G+1) for i in range(P+1)]
        dp[0][0] = 1
        n = len(group)
        for k in range(n):
            g, p = group[k], profit[k]
            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)
            
            
         
#         n = len(group)
#         dp = {\"\":(0, 0)}
#         count = 0
#         for i in range(n):
#             g, p = group[i], profit[i]
#             if g <= G:
#                 for k, v in list(dp.items()):
#                     pg, pp = v
#                     if pg + g <= G:
#                         if pp + p >= P:
#                             count += 1
#                         dp[k+str(i)] = (pg+g, pp+p)
#         return count % (10**9+7)
            
            
        
        


class Solution(object):
    def profitableSchemes(self, G, P, group, profit):
        MOD = 10**9 + 7
        cur = [[0] * (G + 1) for _ in range(P + 1)]
        cur[0][0] = 1

        for p0, g0 in zip(profit, group):
            # p0, g0 : the current crime profit and group size
            cur2 = [row[:] for row in cur]
            for p1 in range(P + 1):
                # p1 : the current profit
                # p2 : the new profit after committing this crime
                p2 = min(p1 + p0, P)
                for g1 in range(G - g0 + 1):
                    # g1 : the current group size
                    # g2 : the new group size after committing this crime
                    g2 = g1 + g0
                    cur2[p2][g2] += cur[p1][g1]
                    cur2[p2][g2] %= MOD
            cur = cur2

        # Sum all schemes with profit P and group size 0 <= g <= G.
        return sum(cur[-1]) % MOD

class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        
        # You have to find what is consecutive. In this problem, the choices of groups are scattered.
        dp = [[0] * (G+1) for i in range(P+1)]
        dp[0][0] = 1
        n = len(group)
        for k in range(n):
            g, p = group[k], profit[k]
            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)
            
            
         
#         n = len(group)
#         dp = {\"\":(0, 0)}
#         count = 0
#         for i in range(n):
#             g, p = group[i], profit[i]
#             if g <= G:
#                 for k, v in list(dp.items()):
#                     pg, pp = v
#                     if pg + g <= G:
#                         if pp + p >= P:
#                             count += 1
#                         dp[k+str(i)] = (pg+g, pp+p)
#         return count % (10**9+7)
            
            
        
        


class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        
        # dp[g][p][c], ways for consider c_th crime, with g gangs to achieve profit p
        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)
    '''
    
    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)

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 # sum(profit) + 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
            #print(*[(i,x) for i,x in enumerate(dp) if x])
        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
        # construct a dp matrix that row, col represents profit and group, entry is number of schemas
        dp = [[0] * (G+1) for _ in range(P+1)]
        dp[0][0] = 1
        for g0, p0 in zip(group, profit):
            # copy previous dp
            dp2 = [row[:] for row in dp]
            for p1 in range(P+1):
                # all schemas >= P will be put in Pth row
                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, 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, max(g - group[i], -1), max(0, p - profit[i]))
        #     b = dp(i + 1, g, p)
        #     return (a + b) % MOD
        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 = [[0] * (P + 1) for i in range(G + 1)]
            for g1 in range(G + 1):
                for p1 in range(P + 1):
                    dp2[g1][p1] = dp[g1][p1]
                    if g1 >= g:
                        dp2[g1][p1] = (dp2[g1][p1] + dp[g1 - g][max(0, p1 - p)]) % MOD
            dp = dp2
        return dp[G][P]

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, 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:
        M = 10**9 + 7
        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[min(i+p, P)][j+g] + dp[i][j]) % M
        
        return sum(dp[P]) % M

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):
            # p0, g0 : the current crime profit and group size
            cur2 = [row[:] for row in cur]
            for p1 in range(P + 1):
                # p1 : the current profit
                # p2 : the new profit after committing this crime
                p2 = min(p1 + p0, P)
                for g1 in range(G - g0 + 1):
                    # g1 : the current group size
                    # g2 : the new group size after committing this crime
                    g2 = g1 + g0
                    cur2[p2][g2] += cur[p1][g1]
                    cur2[p2][g2] %= MOD
            cur = cur2

        # Sum all schemes with profit P and group size 0 <= g <= G.
        return sum(cur[-1]) % MOD

class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        #dp[k][i][j]: # if schemes to achive i profit with j people by assigning first k tasks
        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 = sorted(zip(group, profit))
        gp = list(zip(group, profit))
        # print(gp)
        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
            # print(g, p)
            # print(dp)
        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
                    #     f[a][p][g] = (f[a][p][g]+f[b][p][g])%Mod
                    # else:
                    #     f[a][p][g] = (f[a][p][g]+f[b][p][g])%Mod
            # print(f[a])
        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
                else:
                    if 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)
        # print(Memo)
        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
        '''
        m = {}
        mod = 10**9 + 7
        def dfs(idx, g, p):
            if idx == 0:
                if (idx, g, p) == (0, 0, 0):
                    return 1
                return 0
            #if g <= 0:
            #    return 0
            if (idx, g, p) in m:
                return m[(idx, g, p)]
            res = 0
            res = (dfs(idx-1, g, p) + dfs(idx-1, g-group[idx-1], max(0, p-profit[idx-1])))%mod
            m[(idx, g, p)] = res
            return res
        ans = 0
        for i in range(G+1):
            ans += dfs(len(group), i, P)%mod
        return ans%mod
        '''
        '''
        m = {}
        
        def dfs(idx, g, p):
            res = 0
            if idx == 0:
                if g >= group[0] and profit[0] >= p:
                    res = 1
                return res
            if g <=0:
                return 0
            if p == 0:
                
            if (idx, g, p) in m:
                return m[(idx, g, p)]
            
            res = m[(idx-1, g, p)] + dfs(idx-1, g-group[idx], max(0, p-profit[idx]))
            m[(idx, g, p)] = res
            return res
        '''

class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        
        # dp[g][p][c], ways for consider c_th crime, with g gangs to achieve profit p
        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)
    '''
    
    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)

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)]
        # NOTE: here p and g is not \"budget\", but actual value, to avoid duplication!
        
        # initialization: i = 0
        dp[0][0][0] = 1

        
        # fill the restL i > 0
        for i in range(1, n+1):
            for p in range(P+1):
                for g in range(G+1):
                    # ending at ith crime with p profit lower limit and g group members upper limit
                    dp[i][p][g] = dp[i-1][p][g] # commit or not commit ith crime
                    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:
        ## bottom-up DP: https://www.youtube.com/watch?v=MjOIR61txFc
        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)]
        ## initialization
        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
    
# 5
# 3
# [2,2]
# [2,3]
# 10
# 5
# [2,3,5]
# [6,7,8]
# 1
# 1
# [1,1,1,1,2,2,1,2,1,1]
# [0,1,0,0,1,1,1,0,2,2]
# 100
# 100
# [24,23,7,4,26,3,7,11,1,7,1,3,5,26,26,1,13,12,2,1,7,4,1,27,13,16,26,18,6,1,1,7,16,1,6,2,5,9,19,28,1,23,2,1,3,4,4,3,22,1,1,3,5,34,2,1,22,16,8,5,3,21,1,8,14,2,1,3,8,12,40,6,4,2,2,14,1,11,9,1,7,1,1,1,6,6,4,1,1,7,8,10,20,2,14,31,1,13,1,9]
# [5,2,38,25,4,17,5,1,4,0,0,8,13,0,20,0,28,1,22,7,10,32,6,37,0,11,6,11,23,20,13,13,6,2,36,1,0,9,4,5,6,14,20,1,13,6,33,0,22,1,17,12,10,1,19,13,8,1,0,17,20,9,8,6,2,2,1,4,22,11,3,2,6,0,40,0,0,7,1,0,25,5,12,7,19,4,12,7,4,4,1,15,33,14,2,1,1,61,4,5]


class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        # dp[i][p][g]: number of schemes with g groups and p profit from group[:i].
        
        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:
        MOD = 10**9 + 7
        cur = [[0] * (G + 1) for _ in range(P + 1)]
        cur[0][0] = 1

        for p0, g0 in zip(profit, group):
            # p0, g0 : the current crime profit and group size
            cur2 = [row[:] for row in cur]
            for p1 in range(P + 1):
                # p1 : the current profit
                # p2 : the new profit after committing this crime
                p2 = min(p1 + p0, P)
                for g1 in range(G - g0 + 1):
                    # g1 : the current group size
                    # g2 : the new group size after committing this crime
                    g2 = g1 + g0
                    cur2[p2][g2] += cur[p1][g1]
                    cur2[p2][g2] %= MOD
            cur = cur2

        # Sum all schemes with profit P and group size 0 <= g <= G.
        return sum(cur[-1]) % MOD
            


class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        # backpack problem
        
        # states: subset of schemes profit[1..i], rest members j.
        # dp[i][j][k]: number of schemes ending with i, with rest members j, and rest profit k.
        # transition:  dp[i][j][k] = sum_[l in 1..i-1](dp[l][j+group[j]][k+profit[i]]), k > 0
        #              dp[i][j][0] = sum_[l in 1..i-1; m in 0..profit[i]-1](dp[l][j+group[i]][m])
        # boundary: dp[0][G][P] = 1, dp[i][G][k] = 0
        
#         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(1e9+7)
#         for i in range(1, len(profit)+1):
#             for j in range(G-group[i-1], -1, -1):
#                 for k in range(P-profit[i-1], -profit[i-1]-1, -1):
#                     for l in range(i-1, -1, -1):
#                         dp[i][j][max(0, k)] = (dp[i][j][max(0, k)] + dp[l][j+group[i-1]][k+profit[i-1]]) % mod
                        
#         # print(dp)
#         res = 0
#         for i in range(1, len(profit)+1):
#             for j in range(G+1):
#                 res = (res + dp[i][j][0]) % mod
#         return res
                

# ===================================  
# O(n^4) will cause TLE.
        
        # change k -> at most rest profit k; i -> for 1..i (not ending at)
        # transition: dp[i][j][k] = dp[i-1][j][k] -> not include profit[i]
        #                           + dp[i-1][j+group[i]][k+profit[i]] -> include profit[i]
        # boundary: dp[i][G][P] = 1, dp[i][G][k] = 0.
        
        dp = [[[0 for _ in range(P+1)] for _ in range(G+1)] for _ in range(len(profit)+1)]
        dp[0][-1][-1] = 1
        # for i in range(len(profit)+1):
        #     dp[i][-1][-1] = 1
        
        mod = int(1e9+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: # feasible
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+group[i-1]][min(k+profit[i-1], P)]) % mod
                        
        # print(dp)
        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):

            # no enough people left
            if hc < 0: return 0

            # end of tasks
            if ind >= len(profit): 
                # print(\"hc mp ind\", hc, mp, ind)
                if mp <= 0: return 1
                else: return 0
            
            
            # take this crime
            take = recur(hc - group[ind], max(0, mp - profit[ind]), ind+1)
            # skip this crime
            skip = recur(hc, mp, ind+1)
            
            
            return (take + skip) % (10**9 + 7)
        
        
        return recur(G, P, 0)

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, max(g - group[i], -1), max(0, p - profit[i]))
            b = dp(i + 1, g, p)
            return (a + b) % MOD
        
        n = len(group)
        return dp(0, G, P)

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


            
        


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]
#         # print(psum)
#         @lru_cache(None)
#         def dfs(g, p, idx):
#             if g < 0 or p > psum[idx]:
#                 return 0
#             if idx == n:
#                 return 1
#             res = (dfs(g, p, idx+1) + dfs(g-group[idx], p-profit[idx], idx+1))%MOD
#             # print(g,p,idx,res)
#             return res
#         return dfs(G,P,0)


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]
        # print(psum)
        @lru_cache(None)
        def dfs(g, p, idx):
            # if g < 0 or p > psum[idx]:
            #     return 0
            # if idx == n:
            #     return 1
            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
            # print(g,p,idx,res)
            return res
        return dfs(G,P,0)

# 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]
#         # print(psum)
#         @lru_cache(None)
#         def dfs(g, p, idx):
#             if g < 0 or p > psum[idx]:
#                 return 0
#             if idx == n:
#                 return 1
#             res = (dfs(g, p, idx+1) + dfs(g-group[idx], p-profit[idx], idx+1))%MOD
#             # print(g,p,idx,res)
#             return res
#         return dfs(G,P,0)

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]
        # print(psum)
        @lru_cache(None)
        def dfs(g, p, idx):
            if g < 0 or p > psum[idx]:
                return 0
            if idx == n:
                return 1
            p = max(p,0)
            res = (dfs(g, p, idx+1) + dfs(g-group[idx], p-profit[idx], idx+1))%MOD
            # print(g,p,idx,res)
            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)

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) or member_left <= 0:
                return 0
            take = 0
            if member_left >= group[i]:
                take += (1 if profit[i]+total_profit >= P else 0)
                #take += dp(i+1, total_profit + profit[i], member_left-group[i])
                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)

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) or member_left <= 0:
                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:
        # knapsack
        @lru_cache(None)
        def dp(i,ppl_left,money):
            if ppl_left<0:
                return 0
            if i==len(group):
                return 0
            ret = 0
            # do or dont do this crime
            ret += dp(i+1,ppl_left,money)
            # check if doing this crime can get me above P
            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:
        # Dynamic Programming
        # Time  complexity: O(N x P x G), where N is the number of crimes available to the gang.
        # Space complexity: O(P x G)
        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: 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:
            # newProfit = set()
            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)

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):
            # print(g, p, i)
            if i == n or g == 0: 
                if p == 0: return 1
                return 0

            ans = dp(g, p, i+1)           
            if g - group[i] >= 0:
                ans += dp(g - group[i], max(0, p - profit[i]), i+1)
                
            return ans % (10**9+7)
        
        return dp(G, P, 0) % (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)         #profit
        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]


class Solution(object):
    def profitableSchemes(self, G, P, group, profit):
        MOD = 10**9 + 7
        cur = [[0] * (G + 1) for _ in range(P + 1)]
        cur[0][0] = 1

        for p0, g0 in zip(profit, group):
            # p0, g0 : the current crime profit and group size
            cur2 = [row[:] for row in cur]
            for p1 in range(P + 1):
                # p1 : the current profit
                # p2 : the new profit after committing this crime
                p2 = min(p1 + p0, P)
                for g1 in range(G - g0 + 1):
                    # g1 : the current group size
                    # g2 : the new group size after committing this crime
                    g2 = g1 + g0
                    cur2[p2][g2] += cur[p1][g1]
                    cur2[p2][g2] %= MOD
            cur = cur2

        # Sum all schemes with profit P and group size 0 <= g <= G.
        return sum(cur[-1]) % MOD