Hôm nay, vì sinh nhật Tí, nên mời mọi người đi ăn ở nhà hàng. Mọi việc chuẩn bị gần xong nhưng còn một vấn đề làm Tí khá nhức đầu, đó là làm sao chọn được những món ăn mà mọi người cùng thích. Nhà hàng có ~M~ món ăn khác nhau và thú vị ở chỗ là mỗi món ăn rất nhiều nên có thể đủ cho bao nhiêu người cũng được, vì thế vấn đề là gọi món nào chứ không phải là mỗi món gọi bao nhiêu.

Có tất cả ~N~ người đến dự tiệc sinh nhật (bao gồm cả Tí trong đó). Tí đã tìm hiểu được danh sách những món ăn yêu thích của từng người và muốn rằng đối với mỗi người phải có ít nhất ~2~ món mà họ thích. Tuy nhiên sau khi ăn xong còn nhiều tiết mục hấp dẫn khác nên bạn cũng muốn rằng bất kỳ ai cũng không có quá ~2~ món ăn yêu thích trong danh sách được đặt trước. Và vấn đề cuối cùng, đây là tiền của bố mẹ nên cũng không nên tiêu xài quá đáng.

Yêu cầu:

Hãy cho biết số tiền ít nhất phải trả để gọi một thực đơn thoả mãn các yêu cầu trên.

Input

• Dòng đầu tiên chứa hai số ~M, N~ ~(M<=30; N<=10)~;
• Dòng thứ hai chứa ~M~ số Pi là giá của món thứ ~i~;
• Trong ~N~ dòng cuối cùng, dòng thứ ~k~ ghi danh sách các món yêu thích của người thứ ~k~;

Output

• Gồm một số duy nhất là kết quả của bài toán, hoặc in ra -1 nếu không có cách gọi món nào thoả mãn.

Sample Input

5 3
100 150 300 425 200
1 2 4
1 3 4 5
1 4 5

Sample Output

450