Overview

This is a problem where Takahashi prepares multiple dishes, calculates the score for each dish, and finds the total sum.

Analysis

In this problem, the following calculation needs to be performed for each dish:

• Obtain the base score \(A_{B_j}\) of the base recipe.
• Add the arrangement score \(S_j\) to it to get the dish’s score \(A_{B_j} + S_j\).
• Finally, sum up the scores of all dishes.

The key point here is that the base scores \(A_i\) of the base recipes are given in advance as an array, and we need to quickly retrieve the value corresponding to the index \(B_j\) specified for each dish. Fortunately, all input is given in advance, and no recalculation or modification occurs, so simple array access is sufficiently fast.

A naive but incorrect approach would be to search through the list of base recipes each time to find the corresponding recipe, but this involves unnecessary computation and could potentially exceed the time limit (TLE) in the worst case. However, since array index access can be done in \(O(1)\), we can solve this efficiently by taking advantage of it.

Algorithm

1. First, read the base scores \(A_1, A_2, ..., A_N\) of the base recipes into a list or array.
2. Initialize a variable total_score to 0 to keep track of the total score.
3. For each dish, do the following:
   • Read the base recipe number \(B_j\) and the arrangement score \(S_j\).
   • Add \(A_{B_j - 1}\) (since Python uses 0-based indexing) and \(S_j\), and add the result to total_score.
4. Output the final total_score.

Complexity

• Time complexity: \(O(N + M)\)
  (\(O(N)\) for reading the base recipes, \(O(M)\) for processing each dish)
• Space complexity: \(O(N)\)
  (Memory required to store the array of base recipes)

Implementation Notes

• The base recipe indices are given as 1-based, so you need to subtract 1 when accessing the array (in languages with 0-based indexing such as Python).

• The total score can become very large, so be careful about the range of types such as long long (C++) or Python’s standard integer type.

  Source Code

# 入力の読み込み
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 合計得点の初期化
total_score = 0

# 各料理の得点を計算して合計に加算
for _ in range(M):
    B, S = map(int, input().split())
    total_score += A[B - 1] + S

# 合計得点の出力
print(total_score)

This editorial was generated by qwen3-coder-480b.