Un chatarrero recorre $N$ casas para comprar y vender artículos. Cada casa está numerada del $1$ al $N$. Hay un total de $M$ tipos de artículos que el chatarrero maneja, numerados del $1$ al $M$.

La casa $i$ desea vender al chatarrero $p_i$ artículos de diferentes tipos, uno de cada uno. Los tipos de estos artículos son $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$. El chatarrero puede elegir comprar solo los artículos que desee de entre estos.

Además, la casa $i$ está interesada en $q_i$ tipos diferentes de artículos, que son $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$. La casa $i$ comprará al chatarrero todos los artículos que este tenga de esos tipos. Los tipos de artículos que la casa $i$ vende y los tipos de artículos en los que la casa $i$ está interesada no se solapan entre sí.

El costo para el chatarrero de comprar un artículo de tipo $j$ es $s_j$ por unidad, y el precio de venta es $t_j$ por unidad.

El chatarrero comienza sin ningún artículo y puede visitar las $N$ casas en el orden que desee. Sin embargo, cada casa debe ser visitada exactamente una vez. El chatarrero desea visitar las casas en un orden que maximice su beneficio al finalizar el recorrido. Los artículos que queden después de completar el recorrido no se incluyen en el beneficio. ¿Cuál es el beneficio máximo que se puede obtener?

Entrada

La primera línea contiene $N$ y $M$ separados por un espacio. ($1 \le N \le 18$; $1 \le M \le 100\,000$)

La segunda línea contiene los costos de compra $s_1, \dots, s_M$ separados por espacios.

La tercera línea contiene los beneficios de venta $t_1, \dots, t_M$ separados por espacios. ($1 \le s_j < t_j \le 10^9$)

Las siguientes $2N$ líneas proporcionan información sobre cada casa en orden. La información para la casa $i$ consta de dos líneas:

• La primera línea contiene $p_i$ y $p_i$ enteros $a_{i,1}, \dots, a_{i,p_i}$ separados por espacios. Estos representan los tipos de artículos que la casa $i$ vende.
• La segunda línea contiene $q_i$ y $q_i$ enteros $b_{i,1}, \dots, b_{i,q_i}$ separados por espacios. Estos representan los tipos de artículos en los que la casa $i$ está interesada.

$p_i$ y $q_i$ son enteros no negativos, y satisfacen $0 \le p_i + q_i \le M$.

Para cada $i$, los valores $a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ son enteros distintos entre $1$ y $M$.

Salida

Imprima el beneficio máximo que se puede obtener al visitar las $N$ casas en el orden óptimo.

Ejemplos

Entrada 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

Salida 1

5