Overview

This is a simulation problem where you manage the remaining capacity of each seating area, process fans’ preferred areas in order, and “add the price only if the reservation succeeds.”

Analysis

• Fan \(j\) requests area \(P_j\). If the remaining capacity \(K_{P_j}\) of that area is 1 or more, the reservation succeeds; if it is 0, it fails.
• In other words, all we need to do is keep track of “how many seats remain” for each area, and whenever a request comes in:
  • If seats remain, decrease \(K\) by 1 and add the price \(C\)
  • If no seats remain, do nothing

An alternative approach of counting “how many people applied to each area” afterward and computing \(\min(\text{number of applications}, K_i)\) is also possible, but it still requires aggregation, and processing online (in order) yields the same result.
Since the constraints are \(N, M \le 10^5\), we need to process each fan in \(O(1)\) (for example, searching through a separate data structure each time would be too slow).

Example: - Area 1: \(C_1=100, K_1=2\) - Area 2: \(C_2=200, K_2=1\) - Requests: \([1,2,1,2]\) - 1 → Success (remaining: 1), total: 100 - 2 → Success (remaining: 0), total: 300 - 1 → Success (remaining: 0), total: 400 - 2 → Failure (remaining: 0), total: 400

Algorithm

1. Store the price of area \(i\) in array C[i] and the remaining capacity of area \(i\) in array K[i].
2. Initialize total = 0.
3. For each fan’s requested area \(p\), do the following:
   • If K[p] > 0:
     • K[p] -= 1 (decrease by 1 seat due to reservation)
     • total += C[p] (add the price)
   • Otherwise, do nothing (fully booked, reservation not possible)
4. Output total.

Complexity

• Time complexity: \(O(N + M)\) (reading area information \(N\) times + processing fans \(M\) times, each in \(O(1)\))
• Space complexity: \(O(N)\) (arrays for prices and remaining capacities)

Implementation Notes

• Since the input size is large, in Python it is faster to read all input at once using sys.stdin.buffer.read(), then split() and convert to integers.

• The area numbers \(P_j\) in the input are 1-indexed, so for array access we convert to 0-indexed with p = P_j - 1.

• The maximum total is around \(M \cdot 10^4 \le 10^9\), but Python’s int is arbitrarily large, so there is no need to worry about overflow.

  Source Code

import sys

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

    C = [0] * N
    K = [0] * N
    for i in range(N):
        C[i] = next(it)
        K[i] = next(it)

    total = 0
    for _ in range(M):
        p = next(it) - 1
        if K[p] > 0:
            K[p] -= 1
            total += C[p]

    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.