きたまさの逆襲

有 $n$ 个宝箱，以及可以打开宝箱的 $m$ 把钥匙。第 $i$ 把钥匙可以打开 $k_i$ 个宝箱，分别为 $a_{i, 1}, a_{i, 2}, \dots, a_{i, k_i}$，保证对 $j\neq k$ 有 $a_{i, j}\neq a_{i, k}$。一把钥匙在打开一个宝箱后就会消失，之后无法再使用。有 $d$ 家商店，第 $i$ 把钥匙可以在商店 $s_i$ 买到；购买第 $i$ 把钥匙最开始需要 $c_i$ 元。 小 A 想打开所有的宝箱，所以他需要买钥匙，但他不能买多把相同的钥匙。小 B 想通过涨价的方式阻挠小 A。小 B 可以指定商店 $j$，并将 $j$ 商店出售的所有钥匙的价格同时提升相同的金额；将 $j$ 商店出售的钥匙提升 $1$ 元会花费小 B $b_i$ 元。小 B 所提升的值必须是整数；举例来说，若 $b_j = 2$，小 B 不能花费 $1$ 元将 $j$ 商店出售的钥匙的价格提升 $0.5$ 元。 请找到 $($小 A 的最大花费 $-$ 小 B 的最大花费$)$ 的最大值。若此值可以是无限大，则输出 `-1`。 保证在小 B 不阻挠的情况下小 A 可以打开所有宝箱。 $1\le n\le 100,\ 1\le m\le 1000, \ 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),\ 1\le a_{i, j} \le n$。 ## 输入格式 第一行三个整数，分别表示 $n, m, d$。 接下来 $m$ 行，第 $i$ 行表示第 $i$ 把钥匙的信息。 这 $m$ 行中的第 $i$ 行有 $k_i + 3$ 个整数。前三个整数分别表示 $c_i, s_i, k_i$，随后 $k_i$ 个整数，第 $j$ 个整数表示 $a_{i, j}$。 接下来 $d$ 行，每行一个整数，第 $i$ 行的值表示 $b_i$。 ## 输出格式 一行一个整数，表示所求的最大值。若此值可以是无限大，则输出 `-1`。

[problemUrl]: https://atcoder.jp/contests/utpc2012/tasks/utpc2012_10