1
class Solution {
2
 public:
3
  int dp[102][102][102];
4
  int mod = 1e9 + 7;
5
  int solve(int i, int currPeople, int currProfit, int totalP, int minProfit, vector<int> &group,
6
            vector<int> &profit) {
7
    if (i == profit.size()) {
8
      if (currProfit >= minProfit and totalP >= currPeople) return 1;
9
      return 0;
10
    } else if (totalP < currPeople)
11
      return 0;
12

13
    if (dp[i][currPeople][currProfit] != -1) return dp[i][currPeople][currProfit];
14
    int include = 0, notInclude = 0;
15
    notInclude = solve(i + 1, currPeople, currProfit, totalP, minProfit, group, profit);
16
    include = solve(i + 1, currPeople + group[i], min(currProfit + profit[i], minProfit), totalP,
17
                    minProfit, group, profit);
18
    return dp[i][currPeople][currProfit] = (include % mod + notInclude % mod) % mod;
19
  }
20
  int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit) {
21
    memset(dp, -1, sizeof(dp));
22
    return solve(0, 0, 0, n, minProfit, group, profit);
23
  }
24
};