問題
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