题目描述

下载

小 T 和小 Q 正在打游戏。小 Q 需要击败 $n$ 个 boss，一共有 $m$ 个武器。小 T 开了 $d$ 个商店。第 $i$ 个武器可以被用来击杀 $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ 这些 boss 中的任意一个。但是每个武器只有一个，第 $i$ 个武器当前在商店 $s_i$ 以 $c_i$ 的价格出售，且使用之后就废弃了，不能再被使用。

小 Q 希望以最小的总价格购买若干武器，击杀所有 boss。但小 T 作为商店的老板，可以操纵武器的价格。对于第 $i$ 个商店，小 T 可以花 $b_i$ 的代价将这个商店售卖的每一个武器的价格都增加 $1$。这个操作可以做任意多次，也可以对不同的商店做该操作。

在小 T 完成所有操作后，小 Q 会根据最新的价格购买武器使得能击杀所有 boss。记小 T 付出的代价为 $T$，小 Q 付的钱数量为 $Q$，小 T 希望最大化 $Q-T$，小 Q 希望最小化 $Q-T$，请求出在最优策略下，$Q-T$ 的值。特别地，这个值可能为 $\infty$，此时输出 $-1$。

输入格式

第一行三个整数 $n,m,d$，表示 boss 数量，武器数量，商店数量。

接下来 $m$ 行，每行先有三个整数，$c_i,s_i,k_i$，表示武器的价格，出售它的商店，以及可以击杀 boss 的数量。

然后每行还有 $k_i$ 个整数，$a_{i,1},\cdots,a_{i,k_i}$，表示能击杀哪些 boss。

接下来 $d$ 行，每行一个整数 $b_i$ 表示这个商店提高价格的代价。

输出格式

一行一个整数，表示答案。

样例

样例 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

附加样例

见下发文件，第 $i$ 组下发样例符合第 $i$ 个子任务的限制。

数据范围与约定

对于全部数据，

• $1\le n\le 100,1\le m\le 1000,1\le n,d\le m$
• $1\le b_i,c_i\le 1000,1\le s_i\le d$
• $1\le k_i\le\min(10,n)$
• 数据保证购买所有武器一定能击杀所有 boss。