class Solution:
  def solveKnapsack(self, profits, weights, capacity):
    
    def solve(index, acc_weight, memo):
      if index in memo and acc_weight in memo[index]:
        return memo[index][acc_weight]

      if index == len(profits):
        return 0 

      with_item = 0
      if acc_weight + weights[index] <= capacity:
        with_item = solve(index + 1, acc_weight + weights[index], memo) + profits[index]

      without_item = solve(index + 1, acc_weight, memo)
      
      result =  max(with_item, without_item)
      if index not in memo:
        memo[index] = {}
      memo[index][acc_weight] = result
      return result

    return solve(0, 0, {})