Overview

From the products stored in accessible areas, select up to \(K\) items with the highest prices and find the maximum total price.

Analysis

In this problem, the key question is first “which products can be selected.” Each product belongs to an area, and only products belonging to accessible areas can be chosen.

Therefore, the following steps are necessary:

1. Record the accessible areas (using a set, array, etc.).
2. For each product, determine whether it is in an accessible area.
3. Collect the prices of products that satisfy the condition, and select the \(K\) most expensive ones.

A straightforward approach is to examine all products and check whether each one’s area is permitted — this is sufficiently fast (discussed below). However, if sorting and selection of prices are not done properly, incorrect results or unnecessary computation may occur.

For example, if you select the top \(K\) items without sorting prices in descending order, you may end up with a lower total than the optimal.

Algorithm

1. Read the input and store each product’s price \(V_i\) and area \(C_i\).
2. Manage the accessible area numbers \(S_j\) using a set-type data structure to enable fast lookups.
3. For all products, check whether their area \(C_i\) is accessible.
4. Add to a list only the prices of products in accessible areas.
5. Sort this list in descending order, then take the first \(K\) prices and sum them up.

Concrete Example

For instance, suppose we have the following input:

N=5, M=3, K=3, Q=2
Prices: [100, 200, 50, 300, 150]
Areas: [1, 2, 3, 1, 2]
Accessible: [1, 2]

In this case, the prices of products in area 1 or 2 are [100, 200, 300, 150] — 4 items. Sorting these in descending order gives [300, 200, 150, 100]. Taking the top 3 gives a total of \(300 + 200 + 150 = 650\), which is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the price list)
• Space complexity: \(O(N + Q)\) (storing the product list and accessible areas)

Implementation Notes

• By using a set for checking area membership, \(O(1)\) lookups are possible.

• Since the input can be large, it is recommended to use sys.stdin.read for fast input reading.

• Be careful to specify reverse=True when sorting to ensure descending order.

  Source Code

import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    V = [0] * N
    C = [0] * N
    for i in range(N):
        V[i] = int(data[idx]); idx += 1
        C[i] = int(data[idx]); idx += 1
    
    S = set()
    for _ in range(Q):
        s = int(data[idx]); idx += 1
        S.add(s)
    
    # 立ち入り可能なエリアにある商品の価格をリスト化
    available_prices = []
    for i in range(N):
        if C[i] in S:
            available_prices.append(V[i])
    
    # 価格が高い順にソート
    available_prices.sort(reverse=True)
    
    # 上位K個の合計を計算
    max_sum = sum(available_prices[:K])
    
    print(max_sum)

if __name__ == "__main__":
    main()

---

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