import math

class Solution:
  def countRibbonPieces(self, lengths, total):
    
    def dp(index, acc, count, memo):
      if (index, acc) in memo:
        return memo[(index, acc)]

      if acc > total or index == len(lengths):
        return 0

      if acc == total:
        return count

      with_item = dp(index, acc + lengths[index], count + 1, memo)
      without_item = dp(index + 1, acc, count, memo)

      result = max(with_item, without_item)

      memo[(index, acc)] = result

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