Overview

Given \(N\) types of ingredients (vegetables or meats), with a list of purchasable items provided for each day. The problem asks to independently find the “minimum price of vegetables” and the “minimum price of meats” for each day, and calculate the minimum total cost.

Analysis

The key point of this problem is that “the minimum for each day can be determined by examining only the ingredients available for purchase on that day.”

Key Observation

To find the minimum price satisfying the condition (one vegetable, one meat) for each day, it is sufficient to know the following two things: 1. The minimum price among “vegetables (type 0)” available for purchase on that day 2. The minimum price among “meats (type 1)” available for purchase on that day

If both exist, their sum is the answer for that day. If either one does not exist, the condition cannot be satisfied, so we output \(-1\).

Efficient Processing

“Checking all ingredients every day” would require up to \(M \times N\) computations in the worst case, which would not fit within the time limit. However, looking at the constraints, we see that \(\sum K_j \leq 2 \times 10^5\) (the total number of items across all daily purchase lists).

This means that if we only check the ingredients specified for each day in order, the total number of computations is around \(2 \times 10^5\). Therefore, a straightforward method of scanning the list for each day is more than sufficient.

Algorithm

1. Prepare ingredient data: Store each ingredient’s price \(P_i\) and type \(T_i\) in arrays.
2. Process each day: Repeat the following for \(M\) days:
   • Initialize the minimum vegetable price min_veg and the minimum meat price min_meat to a very large value (infinity).
   • Check each ingredient number available for purchase on that day one by one.
     • If the ingredient is a vegetable, update min_veg with the smaller of the current value and the ingredient’s price.
     • If the ingredient is meat, update min_meat with the smaller of the current value and the ingredient’s price.
   • After the loop, if both min_veg and min_meat have been updated (i.e., are not infinity), output their sum. Otherwise, output \(-1\).

Complexity

• Time complexity: \(O(N + \sum K_j)\)
  • Reading ingredient information takes \(O(N)\), and the total number of ingredient checks across all days is \(O(\sum K_j)\). Since both are around \(2 \times 10^5\) according to the constraints, the solution runs efficiently.
• Space complexity: \(O(N + \sum K_j)\)
  • Memory is needed to store ingredient information and the input shopping lists.

Implementation Notes

• Fast I/O: Since the amount of input data is large, in Python you can significantly reduce execution time by reading all input at once using sys.stdin.read().split() and outputting all at once using sys.stdout.write.

• Handling infinity: For the initial value when updating minimums, use a value sufficiently larger than the maximum price (\(10^9\)), such as 10**18.

• Index adjustment: Ingredient numbers in the problem are 1-indexed (starting from 1), but arrays in programs are typically 0-indexed (starting from 0), so adjustments such as subtracting \(-1\) from the numbers are necessary.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白文字で分割してリスト化します。
    # これにより、大量の入力データを高速に処理できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 全てのトークンを整数に変換します。
    data = list(map(int, input_data))
    
    # N: 食材の種類数, M: 買い物日数
    N = data[0]
    M = data[1]
    
    # 各食材の価格と種類を格納するリストを作成します。
    # 食材番号は1からNで与えられるため、0からN-1のインデックスで管理します。
    prices = [0] * N
    types = [0] * N
    
    # dataリスト内の現在の読み込み位置を示すポインタ
    ptr = 2
    for i in range(N):
        prices[i] = data[ptr]
        types[i] = data[ptr + 1]
        ptr += 2
        
    results = []
    # 最小値を求めるための初期値として、十分大きな値を設定します。
    INF = 10**18
    
    for _ in range(M):
        # その日に購入可能な食材の数 K
        K = data[ptr]
        ptr += 1
        
        min_veg = INF  # 野菜(タイプ0)の最小価格
        min_meat = INF # 肉類(タイプ1)の最小価格
        
        # その日に購入可能な食材を1つずつ確認し、それぞれのタイプの最小価格を更新します。
        for _ in range(K):
            # 食材番号(1-indexed)をインデックス(0-indexed)に変換
            item_idx = data[ptr] - 1
            ptr += 1
            
            p = prices[item_idx]
            t = types[item_idx]
            
            if t == 0:  # 野菜
                if p < min_veg:
                    min_veg = p
            else:       # 肉類
                if p < min_meat:
                    min_meat = p
        
        # 野菜と肉類の両方が見つかった場合、その合計の最小値を記録します。
        # どちらか一方でも見つからない場合は -1 を記録します。
        if min_veg == INF or min_meat == INF:
            results.append("-1")
        else:
            results.append(str(min_veg + min_meat))
    
    # 全ての日付の結果を改行区切りで一括出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.