Overview

This is a problem where you sum up the score \(A_{B_j}+S_j\) for each of \(M\) dishes to find the total score.

Analysis

The score of dish \(j\) is determined by the sum of the “base score of the underlying base recipe” \(A_{B_j}\) and the “arrangement score” \(S_j\). Therefore, the desired total is

[ \sum{j=1}^{M} (A{B_j} + S_j) ]

The key point is that for each dish, all we need to do is look up one value from array \(A\) and add \(S_j\).
For example, if \(A=[10,20,30]\) and \((B,S)=(2,5),(1,-3)\), the scores are \(20+5=25\) and \(10-3=7\), giving a total of \(32\).

A straightforward approach is fast enough, but since \(N,M \le 10^5\), in Python, an implementation that calls input() \(M\) times can become slow due to I/O being a bottleneck. To be safe, use bulk reading with fast input (sys.stdin.buffer.read()).

Algorithm

1. Read \(N, M\).
2. Read array \(A\) (base scores) of length \(N\).
3. Initialize total=0.
4. For each dish \(j=1..M\), read \((B_j, S_j)\):
   • Since \(B_j\) is 1-indexed, convert to 0-indexed: b = B_j - 1
   • Perform total += A[b] + S_j.
5. Output total.

Complexity

• Time complexity: \(O(N+M)\) (\(N\) for reading \(A\), \(M\) for processing each dish)
• Space complexity: \(O(N)\) (storing array \(A\))

Implementation Notes

• Since \(B_j\) is 1-indexed in the input, convert it to B_j-1 for Python array access.

• The total can be as large as \(M \times (10^9 + 10^9) \approx 2 \times 10^{14}\), but Python integers do not overflow, so this can be handled directly.

• Since the input can be large, reading everything at once with sys.stdin.buffer.read().split() and extracting values sequentially using an iterator is fast.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    total = 0
    for _ in range(M):
        b = int(next(it)) - 1
        s = int(next(it))
        total += A[b] + s
    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.