Overview

The set of books that “can be read with at least one” of Aoki’s viewing permits ultimately becomes “all books with difficulty at most the maximum permit level,” so we find that maximum value and sum up the difficulties of the corresponding books.

Analysis

Each viewing permit \(j\) has the property of “allowing reading of all books with difficulty \(L_j\) or less.” The key observation is as follows:

• Let \(X=\max(L_{T_1},\ldots,L_{T_K})\) be the maximum permit level among the permits Aoki holds. Then:
  • A book with difficulty \(p \le X\) can be read using the permit with the maximum level (or any permit with an equal or higher level)
  • A book with difficulty \(p > X\) cannot be read with any permit
    Therefore, “books readable by at least one permit” = “all books with difficulty \(X\) or less.”

A naive approach might be: - For each permit, enumerate and sum up “books with difficulty \(\le L_{T_k}\)” (scanning \(K\) times) - Additionally, handle duplicates (the same book readable by multiple permits)

However, this would be \(O(NK)\) in the worst case, which is too slow given the constraints \(N,M \le 2\times 10^5\). Duplicate management also becomes complex.

Instead, we use the property that “we only need to look at the maximum permit level” to drastically simplify the problem.

(Example) - Book difficulties \(P=[2,5,7]\) - If the permit levels held are \([3,6]\), the maximum is \(6\) - Readable books are those with difficulty \(\le 6\), so the answer is \(2+5=7\)

Algorithm

1. Look at the permit numbers \(T_1,\ldots,T_K\) that Aoki holds, and find the maximum \(X\) of the corresponding permit levels \(L_{T_k}\).
2. For all book difficulties \(P_i\), sum up only those satisfying \(P_i \le X\).
3. Output the sum.

Complexity

• Time complexity: \(O(N+K)\) (including input reading, the overall complexity is \(O(N+M+K)\))
• Space complexity: \(O(N+M+K)\) (for storing arrays)

Implementation Notes

• Permit numbers \(T_k\) are 1-indexed, so when referencing Python arrays, convert to 0-indexed with L[t-1].

• The sum can be as large as \(N \times 10^9\), but since Python’s int has arbitrary precision, we can simply add them without issues.

• Since the input is large, we use sys.stdin.buffer.read() for fast reading.

  Source Code

import sys

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

    P = [next(it) for _ in range(N)]
    L = [next(it) for _ in range(M)]
    T = [next(it) for _ in range(K)]

    max_level = 0
    for t in T:
        lv = L[t - 1]
        if lv > max_level:
            max_level = lv

    ans = 0
    for p in P:
        if p <= max_level:
            ans += p

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.