시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)90393664.286%

문제

고물상이 $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$개의 집을 방문했을 때 얻을 수 있는 최대 수익을 출력한다.

예제 입력 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

출처

University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2022 G번