# Hái thuốc 2

Trung là một thầy thuốc có tiếng. Sau khi chữa trị cho rất nhiều bệnh nhân ngã vì cưỡi VOI, tiếng tăm của Trung ngày càng vươn xa hơn. Vì lượng bệnh nhân đến thăm khám tăng cao, Trung không còn thể tự đi hái thuốc mà phải thuê người thay mình làm việc đó.

Đất nước của trung có $m$ ngọn núi có cây thuốc, ngọn núi thứ $i$ mỗi ngày cho sản lượng $w_i$ kilogam thuốc. Tuy nhiên, các khu rừng giờ đã bị xâm chiếm bởi lũ cướp sẵn sàng tấn công bất kì ai bén mảng đến đây. Những tên cướp này rất giỏi võ, tên cướp trên ngọn núi thứ $i$ thông thạo $a_i$ môn võ. Để đảm bảo an toàn, Trung quyết định sẽ thuê những người linh đánh thuê làm việc cho mình.

Hiện tại, công ty lính đánh thuê có $n$ người lính, người lính thứ $i$ thông thạo $b_i$ môn võ và chi phí để thuê là $c_i$. Để có thể hái thuốc trên một ngọn núi, tất cả những môn võ mà tên cướp trên ngọn núi này biết, đội lính của Trung phải có ít nhất một người cũng biết môn võ đó.

Trong $q$ ngày sắp tới, ngày thứ $i$ Trung cần ít nhất $d_i$ kilogam thuốc để bào chế, tính chi phí ít nhất Trung cần bỏ ra để thuê những người lính. Dữ liệu đảm bảo tồn tại đáp án.

## Input
Dòng đầu tiên chứa số nguyên $m$ là số ngọn núi $(1 \leq m \leq 10^5)$.

Dòng tiếp theo chứa $m$ số nguyên $w_1, w_2, ..., w_m$ lần lượt là sản lượng thuốc trên mỗi ngọn núi $(1 \leq w_i \leq 10^9)$.

$M$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $a_i$ là số môn võ tên cướp trên ngọn núi thứ $i$ thông thạo $(1
\leq a_i \leq 15)$. Tiếp theo là $a_i$ số nguyên $x_1, x_2, ..., x_{a_i}$ mô tả những môn võ mà tên cướp này thông thạo $(1 \leq x_j \leq 15)$.

Dòng tiếp theo chứa số nguyên $n$ là số người lính đánh thuê $(1 \leq n \leq 10^5)$.

Dòng tiếp theo chứa $n$ số nguyên $c_1, c_2, ..., c_n$ lần lượt là chi phí để thuê các người lính $(1 \leq c_i \leq 10^9)$.

$N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $b_i$ là số môn võ người lính thứ $i$ thông thạo $(1
\leq b_i \leq 15)$. Tiếp theo là $a_i$ số nguyên $y_1, y_2, ..., y_{b_i}$ mô tả những môn võ mà người lính này thông thạo $(1 \leq y_j \leq 15)$.

Dòng tiếp theo chứa số nguyên $q$ $(1 \leq q \leq 10^6)$.

$Q$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $d_i$ $(1 \leq d_i \leq 10^9)$.

## Output

In ra $q$ dòng, dòng thứ $i$ là chi phí nhỏ nhất Trung cần bỏ ra trung ngày thứ $i$.

# Lời giải

Chú ý giới hạn $x_j, y_j \leq 15$.

Ta có $sum[mask]$ là tổng lượng thuốc Trung sẽ thu thập được nếu đội lính gồm những người thông thạo các môn võ trong mask. Ta tính $sum[mask]$ bằng kĩ thuật dp SOS.

Ta có $cost[mask]$ là chi phí ít nhất cần bỏ ra để thuê những người lính thông thạo kĩ năng mask. Ta tính $cost[mask]$ bằng cách for submask.

Giờ với mỗi trạng thái mask, ta đã có chi phí và lượng thuốc thu được, sắp xếp theo lượng thuốc thu được tăng dần. Với mỗi ngày, ta chỉ cần chặt nhị phân trên dãy đã sort và tìm đáp án.

ĐPT: $O(2^{15} * 15 + 3^{15} + q \cdot 15)$.