class Solution {
 public:
  int shoppingOffers(vector<int>& price, vector<vector<int>>& special,
                     vector<int>& needs) {
    return dfs(price, special, needs, 0);
  }

 private:
  int dfs(const vector<int>& price, const vector<vector<int>>& special,
          vector<int>& needs, int s) {
    int ans = 0;
    for (int i = 0; i < price.size(); ++i)
      ans += price[i] * needs[i];

    for (int i = s; i < special.size(); ++i)
      if (isValid(special[i], needs)) {
        // use special[i]
        for (int j = 0; j < needs.size(); ++j)
          needs[j] -= special[i][j];
        ans = min(ans, special[i].back() + dfs(price, special, needs, i));
        // backtracking - unuse special[i]
        for (int j = 0; j < needs.size(); ++j)
          needs[j] += special[i][j];
      }

    return ans;
  }

  // check if this special offer is a valid one
  bool isValid(const vector<int>& offer, const vector<int>& needs) {
    for (int i = 0; i < needs.size(); ++i)
      if (needs[i] < offer[i])
        return false;
    return true;
  }
};

class Solution {
  public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    return dfs(price, special, needs, 0);
  }

  private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int s) {
    int ans = 0;
    for (int i = 0; i < needs.size(); ++i)
      ans += needs.get(i) * price.get(i);

    for (int i = s; i < special.size(); ++i) {
      List<Integer> offer = special.get(i);
      if (isValid(offer, needs)) {
        // use special[i]
        for (int j = 0; j < needs.size(); ++j)
          needs.set(j, needs.get(j) - offer.get(j));
        ans = Math.min(ans, offer.get(offer.size() - 1) + dfs(price, special, needs, i));
        // backtracking - unuse special[i]
        for (int j = 0; j < needs.size(); ++j)
          needs.set(j, needs.get(j) + offer.get(j));
      }
    }

    return ans;
  }

  // check if this special offer is a valid one
  private boolean isValid(List<Integer> offer, List<Integer> needs) {
    for (int i = 0; i < needs.size(); ++i)
      if (offer.get(i) > needs.get(i))
        return false;
    return true;
  }
}

class Solution:
  def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
    def dfs(s: int) -> int:
      ans = 0
      for i, need in enumerate(needs):
        ans += need * price[i]

      for i in range(s, len(special)):
        offer = special[i]
        if all(offer[j] <= need for j, need in enumerate(needs)):
          # use special[i]
          for j in range(len(needs)):
            needs[j] -= offer[j]
          ans = min(ans, offer[-1] + dfs(i))
          # backtracking - unuse special[i]
          for j in range(len(needs)):
            needs[j] += offer[j]

      return ans

    return dfs(0)