废品收购商正在巡回 $N$ 个住户以买卖物品。每个住户的编号从 $1$ 到 $N$。废品收购商经营的物品共有 $M$ 种，编号同样从 $1$ 到 $M$。

第 $i$ 个住户希望向废品收购商出售 $p_i$ 种不同的物品，每种物品各一件。这些物品的种类分别为 $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$ 个住户出售的物品种类与他们感兴趣的物品种类互不重叠。

废品收购商收购第 $j$ 种物品的价格为每件 $s_j$，出售的价格为每件 $t_j$。

废品收购商最初处于没有任何物品的状态，可以按任意顺序访问 $N$ 个住户。每个住户必须且只能访问一次。废品收购商希望以能使最终收益最大化的顺序访问住户。巡回结束后剩余的物品不计入收益。请问能获得的最大收益是多少？

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$。($1 \le N \le 18$; $1 \le M \le 100\,000$)

第二行包含 $M$ 个空格分隔的整数 $s_1, \dots, s_M$，表示收购物品的成本。

第三行包含 $M$ 个空格分隔的整数 $t_1, \dots, t_M$，表示出售物品的收益。($1 \le s_j < t_j \le 10^9$)

接下来的 $2N$ 行依次给出每个住户的信息。第 $i$ 个住户的信息由以下两行组成：

• 第一行包含 $p_i$ 和 $p_i$ 个空格分隔的整数 $a_{i,1}, \dots, a_{i,p_i}$，表示第 $i$ 个住户出售的物品种类。
• 第二行包含 $q_i$ 和 $q_i$ 个空格分隔的整数 $b_{i,1}, \dots, b_{i,q_i}$，表示第 $i$ 个住户感兴趣的物品种类。

$p_i, q_i$ 为非负整数，满足 $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