def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
    # 单独购买物品时的价格
    self.price = sum([p * n for p, n in zip(price, needs)])

    # 购买大礼包时比单独购买便宜的价格
    for sp in special:
        sp.append(sp[-1] - sum([p * n for p, n in zip(price, sp[:-1])]))
    # 优先搜索更便宜的大礼包
    special.sort(key=lambda x: x[-1])
    current = 0

    def find(special, needs, current):
        for sp in special:
            if flag(needs, sp):
                sub(needs, sp)
                current += sp[-2]
                # 根据上界剪枝
                if current < self.price:
                    find(special, needs, current)
                current -= sp[-2]
                add(needs, sp)
        t = sum([p * n for p, n in zip(price, needs)])
        # 更新上界
        self.price = min(self.price, current + t)

    def flag(needs, sp):
        for i in range(len(needs)):
            if needs[i] < sp[i]:
                return False
        return True

    def sub(needs, sp):
        for i in range(len(needs)):
            needs[i] -= sp[i]

    def add(needs, sp):
        for i in range(len(needs)):
            needs[i] += sp[i]

    find(special, needs, current)
    return self.price