class Solution {
public:
    int dp[101][1001][6] = {};
    int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount, int maxCoupons) {
        return dfs(price, tastiness, maxAmount, maxCoupons, 0);
    }
    int dfs(vector<int>& p, vector<int>& t, int A, int C, int i) {
        if(i >= p.size())
            return 0;
        if(dp[i][A][C])
            return dp[i][A][C];
        int res = 0;
        int buyWithCoupons = C && (A - (p[i] / 2) >= 0) ? dfs(p, t, A - (p[i] / 2), C - 1, i + 1) + t[i] : 0;
        int buyWithOutCoupons = A - (p[i]) >= 0 ? dfs(p, t, A - p[i], C, i + 1) + t[i] : 0;
        int noBuy = dfs(p, t, A, C, i + 1);
        res = max({buyWithCoupons, buyWithOutCoupons, noBuy});
        return dp[i][A][C] = res;
    }
};