Overview

Among the \(K\) viewing permits that Aoki holds, let \(L_{max}\) be the highest permission level. Then all books with difficulty \(L_{max}\) or less can be viewed. By leveraging this property, we can efficiently compute the sum of difficulties of books that satisfy the condition.

Analysis

Key Insight

Aoki holds multiple viewing permits, but the condition for being able to view a book \(i\) is “there exists at least one permit among the ones he holds whose permission level is at least \(P_i\).”

Rephrasing this, it becomes “the maximum level among the permits he holds is at least \(P_i\).” In other words, if Aoki’s permit numbers are \(T_1, T_2, \ldots, T_K\), then by precomputing $\(L_{max} = \max(L_{T_1}, L_{T_2}, \ldots, L_{T_K})\)\( we can determine whether each book \)i\( is readable simply by checking whether \)Pi \le L{max}$.

Why This Optimization Is Necessary

If we naively check for each book whether any of the \(K\) permits allows reading it, one permit at a time, this requires up to \(N \times K\) comparisons in the worst case. Given the constraints \(N, K \le 2 \times 10^5\), the number of operations can reach up to \(4 \times 10^{10}\), which will not finish within the time limit. By computing the maximum value \(L_{max}\) first, we can drastically reduce the computational complexity.

Algorithm

1. Determine the maximum permission level: Check the permit numbers \(T_1, \ldots, T_K\) that Aoki holds, and find the maximum value \(L_{max}\) among the corresponding levels \(L_{T_k}\).
2. Compute the sum: For each book \(i = 1, \ldots, N\), check its difficulty \(P_i\) in order.
   • If \(P_i \le L_{max}\), the book is readable, so add \(P_i\) to the total.
   • Otherwise, the book is not readable, so skip it.
3. Output the result: Output the final total.

Complexity

• Time complexity: \(O(N + M + K)\)
  • Reading input takes \(O(N + M + K)\).
  • Computing the maximum level \(L_{max}\) takes \(O(K)\).
  • Checking books and computing the sum takes \(O(N)\).
  • Overall, it runs in linear time, which is sufficiently fast.
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the book difficulties and permit levels.

Implementation Notes

• Fast I/O: In Python, when the number of inputs is large (up to about \(6 \times 10^5\) in this problem), reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input().

• Index adjustment: In the problem statement, permit numbers are given as \(1\)-indexed from \(1\) to \(M\), but arrays (lists) in programs are typically \(0\)-indexed, so adjustments like L[t_id - 1] are necessary.

• Handling large numbers: The sum of book difficulties can become a very large value, but since Python’s int type automatically handles arbitrary-precision integers, there is no concern about overflow.

  Source Code

import sys

def main():
    # 競プロにおける高速な入出力のために、sys.stdin.read().split() を使用して
    # すべてのトークンを一度に読み込み、リストに格納します。
    # この手法は、多数の入力を個別に読み込むよりも高速です。
    data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not data:
        return
    
    # N: 本の冊数, M: 閲覧許可証の種類数, K: 青木君が持っている許可証の枚数
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # 閲覧許可証の許可レベル L_j をリストとして取得します。
    # 本の難易度 P_i が N 個あるため、L はインデックス 3 + N から始まります。
    # 許可証番号 T_k で指定されたレベルを効率的に取得するために、int型のリストに変換します。
    L = list(map(int, data[3 + N : 3 + N + M]))
    
    # 青木君が持っている許可証の中で最大の許可レベルを求めます。
    # 青木君が持っている許可証番号 T_k は、インデックス 3 + N + M から始まります。
    # 本を閲覧できる条件は「難易度 <= いずれかの許可レベル」であるため、
    # 保持している許可証の「最大レベル」以下の本はすべて閲覧可能です。
    max_level = 0
    for i in range(3 + N + M, 3 + N + M + K):
        # 許可証番号 T_k は 1-indexed なので、0-indexed のリスト L に合わせるため -1 します。
        t_id = int(data[i])
        level = L[t_id - 1]
        if level > max_level:
            max_level = level
    
    # 青木君が閲覧できる本の難易度の総和を計算します。
    # 本の難易度 P_i はインデックス 3 から 3 + N - 1 までに格納されています。
    ans = 0
    for i in range(3, 3 + N):
        p_val = int(data[i])
        # 本の難易度が青木君の持つ最大許可レベル以下であれば、その本を閲覧できます。
        if p_val <= max_level:
            ans += p_val
    
    # 計算した総和を出力します。
    # Python の int 型は任意精度であるため、大きな合計値でもオーバーフローしません。
    print(ans)

if __name__ == '__main__':
    main()

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