← 返回题目列表

AtCoder · utpc2012_10

J. 北正的反击

中文机器翻译题面 查看原题

問題

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

第一行宝箱数量 n,按键数量 m, 商店数量 给出了 d 。 继续 关键信息在 m 行中给出。 i 行表示, 有第 i 个密钥的信息, 关键价格 c_i, 销售钥匙的商店编号 s_i, 该钥匙可打开的宝箱数量 k_i 按此顺序给出。 进一步 后面是 k_i 整数,这是关键 这是可以用 i 打开的宝箱编号。 继续 d 行给出了提高每个商店的密钥价格所需的成本。

所有数字都从 1 开始。

出力

输出(秋叶同学的必要开支 - 喜多正同学的必要开支)的最大值。 如果答案变得无限大,则打印 -1。

制約

  • 1 \leq n\leq 100, 1\leq m \leq 1000
  • n, d \leq m
  • 保证在没有喜多正的干扰的情况下,秋叶可以打开所有的宝箱。
  • 1 \leq c_i \leq 1000
  • 1 \leq s_i \leq d
  • 1 \leq k_i \leq {\rm min} (10, n)
  • 1 \leq a_{i,j} \leq n
  • j \neq k 如果 a_{i,j} \neq a_{i,k}
  • 1 \leq b_i \leq 1000

部分点

针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。

  • d=1

入力例 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