廃品回収業者が $N$ 個の家を巡回して物品の売買を行う。各家には $1$ から $N$ までの番号が付けられている。業者が取り扱う物品は合計 $M$ 種類あり、同様に $1$ から $M$ までの番号が付けられている。

$i$ 番目の家は、業者に対して $p_i$ 種類の異なる物品をそれぞれ $1$ つずつ販売しようとしている。各物品の種類は $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$ である。業者はこの中から希望する物品のみを選択して買い取ることができる。

また、$i$ 番目の家は $q_i$ 種類の異なる物品に関心を持っており、それぞれ $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$ である。$i$ 番目の家は、業者から該当する種類の物品をいくつでもすべて買い取る。$i$ 番目の家が販売する物品の種類と、$i$ 番目の家が関心を持つ物品の種類は互いに重複しない。

業者が $j$ 番目の種類の物品を買い取る際の価格は $1$ つあたり $s_j$ であり、売る際の価格は $1$ つあたり $t_j$ である。

業者は最初に何も持っていない状態から開始し、$N$ 個の家を好きな順序で訪問できる。ただし、各家は正確に $1$ 回ずつ訪問しなければならない。業者は巡回を終えた時点での利益が最大となるような順序で家を訪問しようとしている。巡回を終えた後に残った物品は利益に含まれない。得られる最大利益はいくらか。

入力

1 行目に $N, M$ が空白区切りで与えられる。($1 \le N \le 18; 1 \le M \le 100\,000$)

2 行目に業者が物品を買い取る際の費用 $s_1, \dots, s_M$ が空白区切りで与えられる。

3 行目に業者が物品を売る際の収益 $t_1, \dots, t_M$ が空白区切りで与えられる。($1 \le s_j < t_j \le 10^9$)

続く $2N$ 行に各家に関する情報が順に与えられる。$i$ 番目の家に関する情報は以下の 2 行からなる。

• 1 行目に $p_i$ と $p_i$ 個の整数 $a_{i,1}, \dots, a_{i,p_i}$ が空白区切りで与えられる。これは $i$ 番目の家が販売する物品の種類を表す。
• 2 行目に $q_i$ と $q_i$ 個の整数 $b_{i,1}, \dots, b_{i,q_i}$ が空白区切りで与えられる。これは $i$ 番目の家が関心を持つ物品の種類を表す。

$p_i, q_i$ は $0$ 以上の整数であり、$0 \le p_i + q_i \le M$ を満たす。

各 $i$ について、$a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ は $1$ 以上 $M$ 以下の互いに異なる整数である。

出力

最適な順序で $N$ 個の家を訪問したときに得られる最大利益を出力する。

入出力例

入力 1

3 4
2 1 3 4
3 2 5 7
2 2 3
1 4
1 3
2 1 2
2 4 1
0

出力 1

5