Bộ Chìa Khóa Tối Thiểu

Có $N$ ổ khóa được đánh số từ $1$ đến $N$. Cửa hàng bán $M$ chìa khóa khác nhau. Chìa khóa thứ $i$ có giá $A_i$ và có thể mở một tập ổ khóa đã biết.

Bạn có thể mua bất kỳ tập con nào trong $M$ chìa khóa, mỗi chìa nhiều nhất một lần. Một chìa đã mua có thể được dùng lại, nhưng mỗi ổ chỉ cần được mở ít nhất một lần.

Hãy tìm tổng tiền nhỏ nhất để mở được toàn bộ $N$ ổ khóa.

Input

• Dòng đầu chứa hai số nguyên $N,M$.
• Với mỗi chìa khóa $i$:
• một dòng chứa $A_i,B_i$ - giá của chìa và số ổ chìa đó mở được;
• dòng kế tiếp chứa $B_i$ số nguyên tăng dần, là chỉ số các ổ khóa được mở.

Output

• In tổng tiền nhỏ nhất để mở được toàn bộ ổ khóa. Nếu không tồn tại cách mua phù hợp, in $-1$.

Constraints

• $1\le N\le 12$.
• $1\le M\le 1000$.
• $1\le A_i\le 10^5$.
• $1\le B_i\le N$.
• Mỗi chỉ số ổ nằm trong $[1,N]$; danh sách của một chìa tăng строго và không lặp.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 8,M\le 18$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3 3
5 2
1 2
4 2
2 3
10 1
3

9