問題一覧 > 通常問題

No.1708 Quality of Contest

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 116
作問者 : chineristACchineristAC / テスター : platinumplatinum 👑 hitonanodehitonanode
5 ProblemId : 5205 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-15 00:31:38

問題文

chinerist 君はプログラミングコンテストを開催しようと思い、 $N$ 問作問しました。各問題にはあらかじめ $1$ から $N$ の番号が割り振られています。

各問題は $0$ 以上の整数であらわされる「クオリティ」と、 $1$ 以上 $M$ 以下の整数であらわされる「ジャンル」の $2$ つの値を持ちます。 問題 $i\ (1\le i\le N)$ のクオリティとジャンルは $A_i,\ B_i$ です。

これらの問題をある順番で出題し、参加者に解いてもらいます。

今回のコンテストの参加者は $K$ 人で、 $i\ (1\le i\le K)$ 人目の参加者は、最初に出題される問題から順に $C_i$ 問解くことがわかっています。

各参加者の「満足度」は $($解いた問題のクオリティの総和$) + X \times ($解いた問題のジャンルの種類数$)$ であらわされます。

参加者の満足度の総和としてありうる値のなかの最大値を求めてください。

入力

$N$ $M$ $X$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
$K$
$C_1$ $C_2$ $\dots$ $C_K$

  • $1 \le N \le 2\times 10^5$
  • $1 \le M \le 2\times 10^5$
  • $0 \le X \le 10^7$
  • $0 \le A_i \le 10^7\ (1\le i \le N)$
  • $1 \le B_i \le M\ (1\le i \le N)$
  • $1 \le K \le 2\times 10^5$
  • $0 \le C_i \le N\ (1\le i \le K)$
  • 与えられる入力はすべて整数

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 2 2
5 1
2 1
1 2
3
1 2 3
出力
29

問題 $1,\ 3,\ 2$ の順番で出題すると満足度の総和が最大になります。

このとき例えば参加者 $2$ の満足度は、解いた問題のクオリティは $5,1$ で、ジャンルの種類は $1,2$ の $2$ 種類なので $(5+1)+2\times 2 = 10$ となります。
サンプル2
入力
3 2 2
10 1
3 2
5 1
3
0 0 0
出力
0

どのような順番で出題しても誰も $1$ 問も解かないので満足度は $0$ です。

サンプル3
入力
15 4 5
6 3
40 1
20 3
5 2
16 3
10 4
21 1
6 2
30 2
5 3
47 1
1 2
5 1
19 4
38 4
6
5 7 1 3 11 12
出力
1168

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。