Overview

You are given the base scores \(A_i\) for \(N\) types of basic recipes, and you need to prepare \(M\) dishes based on them. Each dish’s score is determined by “the score of the base recipe used + the arrangement score,” so the problem asks you to find the total score of all \(M\) dishes.

Analysis

What we want to find is the total sum of the scores of each dish \(j\) (\(1 \le j \le M\)). The score of the \(j\)-th dish can be expressed as \(A_{B_j} + S_j\) as described in the problem statement. Therefore, the final answer is computed by evaluating the following expression:

\[\sum_{j=1}^{M} (A_{B_j} + S_j)\]

Key Points

1. Array Indexing: In the problem statement, the basic recipe numbers are given in 1-indexed format as \(1, 2, \ldots, N\). Since arrays in programming languages (such as Python) typically start from \(0\) (0-indexed), when using the recipe number \(B_j\) as an array index, you need to subtract \(1\) like \(A[B_j - 1]\).

2. Time Complexity and Execution Time: Since \(N\) and \(M\) can be as large as \(10^5\), using nested loops would be too slow. However, the computation for each dish only involves “retrieving a value from the array” and “addition,” so each dish can be processed in \(O(1)\). The overall complexity is \(O(N + M)\), which runs sufficiently fast.

3. Handling Large Numbers: The base scores \(A_i\) and arrangement scores \(S_j\) can be up to \(10^9\), and the number of dishes \(M\) is up to \(10^5\). The total can potentially reach around \(2 \times 10^{14}\). In Python, large integers (arbitrary-precision integers) are handled automatically, but in other languages (such as C++), you need to use a 64-bit integer type (such as long long).

Algorithm

1. Read the number of basic recipes \(N\) and the number of dishes \(M\) from the input.
2. Store the basic recipe scores \(A_1, A_2, \ldots, A_N\) as an array (list).
3. Initialize a variable total_score to \(0\) to hold the total score.
4. Loop \(M\) times, reading the information \((B_j, S_j)\) for each dish.
5. Add \(A[B_j - 1] + S_j\) to total_score.
6. Output the final total_score.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading the recipes takes \(O(N)\), and processing the dishes takes \(O(M)\).
• Space complexity: \(O(N)\)
  • An array of length \(N\) is needed to store the basic recipe scores.

Implementation Notes

• Fast I/O: In Python, when there are many input lines, repeatedly calling input() can lead to long execution times. By using sys.stdin.read().split() to read all input at once and processing it as a list, you can significantly reduce execution time.

• Handling 1-indexed values: If you use the recipe number \(B_j\) directly as an array index, it will cause an out-of-bounds error (IndexError) or reference the wrong recipe, so you must always adjust by subtracting \(-1\).

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    # これにより、大量の入力行を高速に処理できる
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 基本レシピの数 N と料理の数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各基本レシピの基本点 A_i をリストとして取得
    # input_data[2] から input_data[2 + N - 1] までが A_1, ..., A_N
    # 0-indexed になるため、レシピ番号 b に対しては A[b-1] でアクセスする
    A = list(map(int, input_data[2:2+N]))
    
    total_score = 0
    
    # 料理の情報を順番に処理する
    # 各料理の情報 (B_j, S_j) は input_data[2 + N] 以降にペアで並んでいる
    current_ptr = 2 + N
    for _ in range(M):
        # ベースにするレシピの番号 B_j (1-indexed)
        b_j = int(input_data[current_ptr])
        # アレンジ点 S_j
        s_j = int(input_data[current_ptr + 1])
        
        # 料理の得点 = A[B_j - 1] + S_j を合計に加算
        total_score += A[b_j - 1] + s_j
        
        # 次の料理の情報へポインタを進める
        current_ptr += 2
        
    # 合計得点を出力
    print(total_score)

if __name__ == '__main__':
    solve()

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