class Solution:
    def shoppingOffers(self, price, special, needs):
        d = {}
        def dp(i, needs):
            if (i, needs) in d:
                return d[(i, needs)]
            if i == len(special):
                return sum(n*price[i] for i, n in enumerate(needs))
            needs = list(needs)
            best = float('inf')
            k = 0
            while True:
                best = min(best, k*special[i][-1]+dp(i+1, tuple(needs)))
                for j in range(len(needs)):
                    needs[j] -= special[i][j]
                    if needs[j] < 0:
                        d[(i, tuple(needs))] = best
                        return best
                k += 1
        return dp(0, tuple(needs))

print(Solution().shoppingOffers([2,5], [[3,0,5],[1,2,10]], [3,2]))
print(Solution().shoppingOffers([2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]))
