Overview

For each day, the problem asks you to find the minimum total cost when selecting one vegetable (\(T=0\)) and one meat (\(T=1\)) from the ingredients available that day. If either type is unavailable, output \(-1\).

Analysis

Key Insight

The answer for each day is determined simply by finding: - The cheapest vegetable among the ingredients available that day - The cheapest meat among the ingredients available that day

and adding them together.

This works because the only condition is “one type of vegetable + one type of meat,” with no other constraints (such as buying the same ingredient multiple times, compatibility, quantity limits, etc.). Therefore, the optimal solution is to independently “choose the cheapest vegetable” and “choose the cheapest meat.”

Why a Naive Approach Can Fail

• It’s natural to look through the candidate ingredient list for each day to find the cheapest pair, but if you implement it as “search through all ingredients every day” (\(O(N)\) per day), the worst case becomes \(O(NM)\), which is far too slow for \(2\times 10^5\).
• In this problem, there is a constraint on the total number of candidates \(K_j\) across all days: \(\sum K_j \le 2\times 10^5\). This means that if we adopt the approach of “only iterating through the given candidates,” we can achieve fast execution.

Solution

For each day, scan only the candidate ingredients given in the input, and update: - The minimum price for \(T=0\): min0 - The minimum price for \(T=1\): min1

If either one doesn’t exist, output \(-1\). If both exist, the answer is min0 + min1.

Example: If the candidates for a day are: - Vegetables: 120 yen, 200 yen - Meat: 300 yen, 250 yen

then the minimum is \(120 + 250 = 370\) yen.

Algorithm

1. Store the price \(P_i\) and type \(T_i\) for each ingredient in arrays.
2. For each day, do the following:
   • Initialize min0 = INF, min1 = INF
   • Read the candidate ingredient numbers \(s\) for that day in order:
     • If \(T_s=0\), update min0 = min(min0, P_s)
     • If \(T_s=1\), update min1 = min(min1, P_s)
   • If min0 or min1 has not been updated, output -1
   • Otherwise, output min0 + min1
3. Since the input is large, read it all at once using fast input (sys.stdin.buffer.read()) and consume it with an iterator.

Complexity

• Time complexity: \(O\!\left(N + \sum_{j=1}^{M} K_j\right)\) (Each ingredient’s information is read once, and each day’s candidate ingredients are processed once in total)
• Space complexity: \(O(N)\) (Arrays for \(P\) and \(T\))

Implementation Notes

• Use a sufficiently large value for INF (e.g., \(10^{30}\)) to determine “whether the minimum was updated.”

• Since all we need for each day is “the minimum vegetable price” and “the minimum meat price,” we can update on the fly without storing candidates, saving memory.

• Due to the large input size, in Python it is more reliably fast to read all input at once with sys.stdin.buffer.read() rather than repeatedly calling input().

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    P = [0] * (N + 1)
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = next(it)
        T[i] = next(it)

    INF = 10**30
    out_lines = []
    for _ in range(M):
        k = next(it)
        min0 = INF
        min1 = INF
        for _ in range(k):
            s = next(it)
            if T[s] == 0:
                if P[s] < min0:
                    min0 = P[s]
            else:
                if P[s] < min1:
                    min1 = P[s]
        if min0 == INF or min1 == INF:
            out_lines.append("-1")
        else:
            out_lines.append(str(min0 + min1))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.