class Solution {
public:
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        const int MOD = 1000000007;
        int n = group.size();
        //dp[i][j][k] represents the ways we can get profit k
        //with j people in tasks [0, i]
        //dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]
        //rolling array to save spaces
        int e = 0;
        vector<unordered_map<int, unordered_map<int, int>>> dp(2);
        for(int i = 0; i < n; ++i, e ^= 1)
        {
            int currG = group[i], currP = profit[i];
            if(i)dp[e] = dp[e ^ 1];
            if(currG <= G)++dp[e][currG][min(P, currP)];
            for(auto& p1 : dp[e ^ 1])
            {
                int usedG = p1.first;
                if(currG <= G - usedG)
                {
                    for(auto& p2 : p1.second)
                    {
                        //having the upperbound of newP can save time
                        int gainedProfit = p2.first, newP = gainedProfit + currP >= P? P: gainedProfit + currP;
                        dp[e][currG + usedG][newP] += p2.second;
                        dp[e][currG + usedG][newP] %= MOD;
                    }
                }
            }
        }
        int res = 0;
        for(auto& p1 : dp[e ^ 1])
        {
            res += p1.second[P];
            res %= MOD;
            
        }
        return res;
    }
};