class Solution:
  def solveKnapsack(self, profits, weights, capacity):

    def dp(index, acc, weight, memo):

      if (index, acc, weight) in memo:
        return memo[(index, acc, weight)]

      if index == len(profits):
        return acc
      
      result = 0
      if weight + weights[index] <= capacity:
        same_index = dp(index, acc + profits[index], weight + weights[index], memo)
        skip_index = dp(index + 1, acc, weight, memo)
        result = max(same_index, skip_index)
      
      else:
        result = dp(index + 1, acc, weight, memo) # skip index 

      memo[(index, acc, weight)] = result
      return result

    return dp(0, 0, 0, {})