Giải bài trực tuyến

Hàng năm vì muốn có không khí ấm cúng và cũng để tiết kiệm nên bạn thường tổ chức sinh nhật ở nhà. Tuy nhiên trước sinh nhật năm nay vài hôm bạn đã thi đậu vào đội tuyển tin học quốc gia. Đây là một sự kiện đặc biệt có ý nghĩa nên bạn quyết định mừng ngày sinh nhật của mình tại một nhà hàng Trung Quốc sang trọng và bạn tự nhủ lần này nhất định phải tiêu xài rộng tay hơn. Mọi việc chuẩn bị đã gần xong nhưng còn một vấn đề làm bạn 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 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ả bạn trong đó). Bạn đã tìm hiểu được danh sách những món ăn yêu thích của từng người và bạn 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 thỏa mãn các yêu cầu trên.

Dữ liệu

- Dòng đầu tiên chứa hai số M, N
- Dòng thứ hai chứa M số P_i 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.

Kết quả

- 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 thỏa mãn.

Ví dụ

Dữ liệu:
5 3
100 150 300 425 200
1 2 4
1 3 4 5
1 4 5

Kết quả:
450

Giới hạn

- M ≤ 30.
- N ≤ 10.