For convenience, let's think in terms of `value`

, the discount each special offer gives from the nominal price. (The values in this array are non-positive.)

Our goal is to minimize the sum of our discount. Our top-down dp function, `discount`

, will do this. Suppose we are currently considering the ith special offer, and we have some order. We must use some legal number of this offer special[i]: if we use K of them, then we will get a discount of `K * value[i]`

, and in turn this will specify the candidates for our dp.

Let's also memoize to reduce repeated work - there are up to 7^6 * 100 = about 11 million states, which will fit memory.

```
def shoppingOffers(self, price, special, needs):
def nominal_price(offer):
return sum(p * offer[i] for i, p in enumerate(price))
value = [offer.pop() - nominal_price(offer) for offer in special]
memo = {}
def discount(i, *order):
if i == len(special):
return 0
if (i, order) not in memo:
ans = discount(i+1, *order)
val = 0
cur_order = order[:]
while True:
cur_order = map(operator.sub, cur_order, special[i])
val += value[i]
if any(x < 0 for x in cur_order): break
ans = min(ans, val + discount(i+1, *cur_order))
memo[i, order] = ans
return memo[i, order]
return nominal_price(needs) + discount(0, *needs)
```