東京大学プログラミングコンテスト2012

J - きたまさの逆襲


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

n個の宝箱とそれを開けるためのm個の鍵がd個のお店で売られている.鍵iは宝箱a_{i,1},...,a_{i,k_i}を開けることができ,宝箱を開けると鍵は消滅してしまう.鍵iの値段はc_i円であり,お店s_iで売られている.秋葉さんは全ての宝箱を開けるために鍵を買うことを考えている.ただし同じ鍵を複数買うことはできない.きたまささんは秋葉さんの邪魔をするために鍵の値段を釣り上げようとしている.一度に一つのお店で売られている鍵の値段を全て同じだけ釣り上げることができ,お店jで売られている鍵の値段を1円釣り上げるのにかかる費用はb_jである.釣り上げ幅は非負整数でなければならない.例えばb_j=2の場合に,1円使って値段を0.5円釣り上げるなどということはできない.うまいこと釣り上げて,(秋葉さんの必要な費用-きたまささんの必要な費用)を最大化せよ.答えが無限に大きくなる場合は-1を出力せよ.ただし,きたまささんの妨害がない場合に秋葉さんが全ての宝箱を開けることができることは保証されている.


入力

n m d
c_1 s_1 k_1 a_{1,1} ... a_{1,k_1}
...
c_m s_m k_m a_{m,1} ... a_{m,k_m}
b_1
...
b_d

1行目に 宝箱の数 n, 鍵の数 m, 店の数 d が与えられる. 続く m 行に鍵の情報が与えられる. i 行目には, i 番目の鍵の情報があり, 鍵の値段 c_i, 鍵を売っている店の番号 s_i, その鍵で開けられる宝箱の数 k_i がこの順で与えられる. さらに k_i 個の整数が続き, これらは鍵 i で開けられる宝箱の番号である. 続く d 行に, 各店で鍵の値段を上げるのに必要なコストが与えられる.

すべての番号は1から始まる.

出力

(秋葉さんの必要な費用-きたまささんの必要な費用)の最大値を出力せよ. 答えが無限に大きくなる場合は-1を出力せよ.

制約

部分点

この問題の判定には,50 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす.


入力例 1

3 4 1
2 1 2 1 2
2 1 2 2 3
2 1 2 3 1
3 1 3 1 2 3
5

入力例 1 に対する出力例

6

入力例 2

3 4 1
2 1 2 1 2
2 1 2 2 3
2 1 2 3 1
3 1 3 1 2 3
2

入力例 2 に対する出力例

-1

入力例 3

2 3 2
3 1 2 1 2
4 1 1 2
5 2 2 1 2
1
2

入力例 3 に対する出力例

8

Submit提出する