Traveling Junkman Problem

고물상이 $N$개의 집을 순회하며 물건을 사고 판다. 각 집에는 $1$번부터 $N$번까지 번호가 붙어 있다. 고물상이 취급하는 물건은 총 $M$종류가 있으며, 마찬가지로 $1$번부터 $M$번까지 번호가 붙어 있다.

$i$번 집은 고물상에게 $p\_i$가지 서로 다른 종류의 물건을 하나씩 판매하고자 한다. 각 물건의 종류는 $a\_{i,1}$, $a\_{i,2}$, $\cdots$, $a\_{i,p\_i}$번이다. 고물상은 이 중 원하는 물건들만 선택해서 매입할 수 있다.

또한 $i$번 집은 $q\_i$가지 서로 다른 종류의 물건에 관심이 있으며, 각각 $b\_{i,1}$, $b\_{i,2}$, $\cdots$, $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,\cdots ,s\_M$이 공백으로 구분되어 주어진다.

세 번째 줄에 고물상이 물건을 판매할 때 버는 수익 $t\_1,\cdots ,t\_M$이 공백으로 구분되어 주어진다. $(1\le s\_j\<t\_j\le 10^9)$

다음 $2N$개 줄에 각 집에 대한 정보가 순서대로 주어진다. $i$번 집에 대한 정보는 다음과 같이 두 줄로 이루어진다.

• 첫 번째 줄에 $p\_i$와 $p\_i$개의 정수 $a\_{i,1},\cdots ,a\_{i,p\_i}$가 공백으로 구분되어 주어진다. $i$번 집이 판매하는 물건의 종류를 나타낸다.
• 두 번째 줄에 $q\_i$와 $q\_i$개의 정수 $b\_{i,1},\cdots ,b\_{i,q\_i}$가 공백으로 구분되어 주어진다. $i$번 집이 관심을 가지는 물건의 종류를 나타낸다.

$p\_i,q\_i$는 $0$ 이상의 정수이며, $0\le p\_i+q\_i\le M$을 만족한다.

각 $i$에 대해서 $a\_{i,1},\cdots ,a\_{i,p\_i},b\_{i,1},\cdots ,b\_{i,q\_i}$는 $1$ 이상 $M$ 이하의 서로 다른 정수이다.

최적의 순서로 $N$개의 집을 방문했을 때 얻을 수 있는 최대 수익을 출력한다.