Một người buôn đồng nát đi thăm $N$ ngôi nhà để mua và bán hàng hóa. Mỗi ngôi nhà được đánh số từ $1$ đến $N$. Có tổng cộng $M$ loại hàng hóa mà người buôn đồng nát kinh doanh, cũng được đánh số từ $1$ đến $M$.

Ngôi nhà thứ $i$ muốn bán cho người buôn đồng nát $p_i$ loại hàng hóa khác nhau, mỗi loại một đơn vị. Các loại hàng hóa đó là $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$. Người buôn đồng nát có thể chọn mua bất kỳ loại hàng hóa nào trong số này.

Ngoài ra, ngôi nhà thứ $i$ quan tâm đến $q_i$ loại hàng hóa khác nhau, lần lượt là $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$. Ngôi nhà thứ $i$ sẽ mua sạch tất cả các đơn vị hàng hóa thuộc các loại này mà người buôn đồng nát có. Các loại hàng hóa mà ngôi nhà thứ $i$ bán và các loại hàng hóa mà ngôi nhà thứ $i$ quan tâm không bao giờ trùng nhau.

Giá mua vào của người buôn đồng nát đối với hàng hóa loại $j$ là $s_j$ mỗi đơn vị, và giá bán ra là $t_j$ mỗi đơn vị.

Người buôn đồng nát bắt đầu với việc không có hàng hóa nào trong tay và có thể thăm $N$ ngôi nhà theo bất kỳ thứ tự nào. Tuy nhiên, mỗi ngôi nhà phải được thăm chính xác một lần. Người buôn đồng nát muốn chọn thứ tự thăm các ngôi nhà sao cho lợi nhuận thu được là lớn nhất sau khi hoàn thành chuyến đi. Những hàng hóa còn dư lại sau chuyến đi sẽ không được tính vào lợi nhuận. Lợi nhuận tối đa có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa $N$ và $M$ cách nhau bởi dấu cách. ($1 \le N \le 18$; $1 \le M \le 100\,000$)

Dòng thứ hai chứa chi phí mua vào $s_1, \dots, s_M$ cách nhau bởi dấu cách.

Dòng thứ ba chứa lợi nhuận bán ra $t_1, \dots, t_M$ cách nhau bởi dấu cách. ($1 \le s_j < t_j \le 10^9$)

$2N$ dòng tiếp theo chứa thông tin về mỗi ngôi nhà theo thứ tự. Thông tin về ngôi nhà thứ $i$ bao gồm hai dòng:

• Dòng đầu tiên chứa $p_i$ và $p_i$ số nguyên $a_{i,1}, \dots, a_{i,p_i}$ cách nhau bởi dấu cách, biểu thị các loại hàng hóa mà ngôi nhà thứ $i$ bán.
• Dòng thứ hai chứa $q_i$ và $q_i$ số nguyên $b_{i,1}, \dots, b_{i,q_i}$ cách nhau bởi dấu cách, biểu thị các loại hàng hóa mà ngôi nhà thứ $i$ quan tâm.

$p_i, q_i$ là các số nguyên không âm và thỏa mãn $0 \le p_i + q_i \le M$.

Với mỗi $i$, các giá trị $a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ là các số nguyên phân biệt nằm trong khoảng từ $1$ đến $M$.

Dữ liệu ra

In ra lợi nhuận tối đa có thể đạt được khi thăm $N$ ngôi nhà theo thứ tự tối ưu.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

5