$n$ 個の箱（$1$ から $n$ まで番号付け）、$m$ 個の鍵（$1$ から $m$ まで番号付け）、および $d$ 個の店（$1$ から $d$ まで番号付け）がある。鍵 $i$ は箱 $a_{i,1}, \dots, a_{i,k_i}$ のいずれか一つを開けるために使用できる。ただし、鍵は一度箱を開けるために使用すると消滅する。したがって、一つの鍵で複数の箱を開けることはできない。鍵 $i$ は店 $s_i$ で売られており、その価格は $c_i$ ドルである。Akiba はいくつかの鍵を購入し、すべての箱を開けたいと考えている。（同じ鍵を複数回購入することはできない。）

Kitamasa はこれを阻止したいと考えている。そのために、Akiba がどの鍵を購入するかを決める前に、いくつかの鍵の価格を変更することができる。Kitamasa が $b_j$ ドル支払うと、店 $j$ で売られているすべての鍵の価格を 1 ドル引き上げることができる。各店について、この操作を任意の非負整数回繰り返すことができる。例えば、$2b_j$ ドル支払えば、店 $j$ で売られているすべての鍵の価格を 2 ドル引き上げることができる。ただし、例えば $b_j = 2$ の場合、1 ドル支払って価格を 0.5 ドル変更することはできない。

Akiba の目的は (Akiba の支払い) − (Kitamasa の支払い) を最小化することであり、Kitamasa の目的はそれを最大化することである。両者が最適に行動したときのこの値を計算せよ。答えが無限に大きくなる場合は $-1$ を出力せよ。Kitamasa が何もしなかった場合、Akiba がすべての箱を開けられることは保証されている。

入力

入力の最初の行には、3 つの整数 $n, m, d$ ($1 \le m \le 1000, n \le 100, 1 \le n, d \le m$) が含まれる。

続く $m$ 行は、各鍵について記述する。各行は 3 つの整数で始まる：鍵の価格 $c_i$、鍵が売られている店の番号 $s_i$、この鍵で開けられる箱の数 $k_i$。続いて $k_i$ 個の整数が続く：これらの箱の番号 ($1 \le 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$)。

続く $d$ 行には、それぞれ 1 つの整数 $b_i$ ($1 \le b_i \le 1000$) が含まれる。

出力

問題の答えである整数を 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