Скупщик металлолома посещает $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$, и типы товаров, в которых заинтересован дом $i$, не пересекаются.

Стоимость покупки скупщиком товара типа $j$ составляет $s_j$ за единицу, а цена продажи — $t_j$ за единицу.

Скупщик начинает путь, не имея при себе никаких товаров, и может посещать $N$ домов в любом порядке. Однако каждый дом должен быть посещен ровно один раз. Скупщик хочет выбрать такой порядок посещения домов, который максимизирует его прибыль после завершения обхода. Товары, оставшиеся после завершения обхода, в прибыль не включаются. Какую максимальную прибыль можно получить?

Входные данные

В первой строке заданы $N$ и $M$, разделенные пробелом ($1 \le N \le 18$; $1 \le M \le 100\,000$).

Во второй строке заданы стоимости покупки $s_1, \dots, s_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