A junkman travels through $N$ houses to buy and sell goods. Each house is numbered from $1$ to $N$. There are $M$ types of goods in total, also numbered from $1$ to $M$.

House $i$ wants to sell $p_i$ different types of goods, one of each. The types of these goods are $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$. The junkman can choose to buy any subset of these goods.

Additionally, house $i$ is interested in $q_i$ different types of goods, which are $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$. House $i$ will buy all available goods of these types from the junkman. The types of goods that house $i$ sells and the types of goods that house $i$ is interested in are disjoint.

The cost for the junkman to buy one unit of good type $j$ is $s_j$, and the selling price is $t_j$.

The junkman starts with no goods and can visit the $N$ houses in any order. Each house must be visited exactly once. The junkman wants to visit the houses in an order that maximizes the total profit upon completing the tour. Goods remaining after the tour are not included in the profit. What is the maximum profit that can be obtained?

Input

The first line contains $N$ and $M$ separated by a space. ($1 \le N \le 18$; $1 \le M \le 100\,000$)

The second line contains the costs $s_1, \dots, s_M$ to buy the goods, separated by spaces.

The third line contains the profits $t_1, \dots, t_M$ earned from selling the goods, separated by spaces. ($1 \le s_j < t_j \le 10^9$)

The next $2N$ lines provide information about each house in order. Information for house $i$ consists of two lines:

• The first line contains $p_i$ and $p_i$ integers $a_{i,1}, \dots, a_{i,p_i}$ separated by spaces. This represents the types of goods that house $i$ sells.
• The second line contains $q_i$ and $q_i$ integers $b_{i,1}, \dots, b_{i,q_i}$ separated by spaces. This represents the types of goods that house $i$ is interested in.

$p_i$ and $q_i$ are non-negative integers, satisfying $0 \le p_i + q_i \le M$.

For each $i$, $a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ are distinct integers between $1$ and $M$.

Output

Output the maximum profit that can be obtained by visiting the $N$ houses in an optimal order.

Examples

Input 1

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

Output 1

5