B - Product Selection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はデパートのバイヤーです。今度開催される特別セールに向けて、倉庫から商品を選んで売り場に並べることになりました。

倉庫には N 個の商品があり、i 番目の商品 (1 \leq i \leq N) には販売価格 V_i が設定されています。また、倉庫は 1 から M までの番号が付いた M 個のエリアに分かれており、i 番目の商品はエリア C_i に保管されています。

倉庫のエリアの中には改装工事中のため立ち入ることができないものがあります。立ち入り可能なエリアは Q 個あり、そのエリア番号は S_1, S_2, \ldots, S_Q として与えられます。これら以外のエリアには立ち入ることができません。

高橋君は、立ち入り可能なエリアに保管されている商品の中から K 個以下（0 個でもよい）を選んで売り場に並べます。各商品は最大 1 回しか選べません。売り場のスペースの都合上、K 個を超える商品を並べることはできません。

売り場に並べる商品の販売価格の合計の最大値を求めてください。なお、商品を 1 個も並べない場合の販売価格の合計は 0 とします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq N
  • 1 \leq Q \leq M
  • 1 \leq V_i \leq 10^9
  • 1 \leq C_i \leq M
  • 1 \leq S_j \leq M
  • S_1, S_2, \ldots, S_Q はすべて異なる
  • 入力はすべて整数

入力

N M K Q
V_1 C_1
V_2 C_2
\vdots
V_N C_N
S_1 S_2 \ldots S_Q
  • 1 行目には、商品の数 N、エリアの数 M、売り場に並べられる商品の最大数 K、立ち入り可能なエリアの数 Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の商品の販売価格 V_i と、その商品が保管されているエリア番号 C_i が、スペース区切りで与えられる。
  • 最後の行には、立ち入り可能なエリアの番号 S_1, S_2, \ldots, S_Q が、スペース区切りで与えられる。

出力

売り場に並べる商品の販売価格の合計の最大値を 1 行で出力せよ。

入力例 1

5 3 2 2
100 1
200 2
150 1
300 3
50 2
1 2

出力例 1

350

入力例 2

8 5 4 3
500 1
300 2
800 3
150 4
600 2
250 5
400 1
100 3
2 3 5

出力例 2

1950

入力例 3

12 6 5 4
1000000000 1
999999999 2
888888888 3
777777777 4
666666666 5
555555555 6
444444444 1
333333333 2
222222222 3
111111111 4
100000000 5
50000000 6
1 2 4 6

出力例 3

3777777775

Score : 300 pts

Problem Statement

Takahashi is a buyer for a department store. For an upcoming special sale, he needs to select products from the warehouse and display them on the sales floor.

There are N products in the warehouse, and the i-th product (1 \leq i \leq N) has a selling price of V_i. The warehouse is divided into M areas numbered from 1 to M, and the i-th product is stored in area C_i.

Some areas of the warehouse are inaccessible due to renovation work. There are Q accessible areas, and their area numbers are given as S_1, S_2, \ldots, S_Q. All other areas are inaccessible.

Takahashi will select at most K products (possibly 0) from those stored in accessible areas and display them on the sales floor. Each product can be selected at most once. Due to space limitations on the sales floor, no more than K products can be displayed.

Find the maximum possible total selling price of the products displayed on the sales floor. Note that if no products are displayed, the total selling price is 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq N
  • 1 \leq Q \leq M
  • 1 \leq V_i \leq 10^9
  • 1 \leq C_i \leq M
  • 1 \leq S_j \leq M
  • S_1, S_2, \ldots, S_Q are all distinct
  • All inputs are integers

Input

N M K Q
V_1 C_1
V_2 C_2
\vdots
V_N C_N
S_1 S_2 \ldots S_Q
  • The first line contains the number of products N, the number of areas M, the maximum number of products that can be displayed K, and the number of accessible areas Q, separated by spaces.
  • The i-th of the following N lines (1 \leq i \leq N) contains the selling price V_i of the i-th product and the area number C_i where it is stored, separated by a space.
  • The last line contains the area numbers of the accessible areas S_1, S_2, \ldots, S_Q, separated by spaces.

Output

Print the maximum possible total selling price of the products displayed on the sales floor in a single line.

Sample Input 1

5 3 2 2
100 1
200 2
150 1
300 3
50 2
1 2

Sample Output 1

350

Sample Input 2

8 5 4 3
500 1
300 2
800 3
150 4
600 2
250 5
400 1
100 3
2 3 5

Sample Output 2

1950

Sample Input 3

12 6 5 4
1000000000 1
999999999 2
888888888 3
777777777 4
666666666 5
555555555 6
444444444 1
333333333 2
222222222 3
111111111 4
100000000 5
50000000 6
1 2 4 6

Sample Output 3

3777777775