旅行廢品商問題 - Problem

廢品回收商正在巡迴 $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$ 個住家出售的物品種類與其感興趣的物品種類之間沒有重疊。

回收商買入第 $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$ 個住家後所能獲得的最大利潤。

QOJ.ac