class Solution:
  def solveRodCutting(self, lengths, prices, n):
    def dp(index, acc, length, memo):

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

      if index == len(lengths):
        return acc
      
      result = 0

      if length + lengths[index] <= n:
        
        with_item = dp(index, acc + prices[index], length + lengths[index], memo)
        without_item = dp(index + 1, acc, length, memo)
        result = max(with_item, without_item)
      else:
        result = dp(index + 1, acc, length, memo) # without item // skipping 
        
      memo[(index, acc, length)] = result

      return result

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