Những chiếc rương và chìa khóa

Alice và Bob chơi một trò chơi. Alice có $n$ rương kho báu, rương thứ $i$ chứa $a_i$ đồng xu, và $m$ loại chìa khóa. Chìa khóa loại $j$ có thể được bán cho Bob với giá $b_j$ đồng xu.

Đầu tiên, Alice đặt các ổ khóa lên những chiếc rương. Có $m$ loại ổ khóa, ổ khóa loại $j$ chỉ có thể được mở bằng chìa khóa loại $j$. Để đặt một ổ khóa loại $j$ lên rương $i$, Alice phải trả $c_{i,j}$ USD. Alice có thể đặt bất kỳ số loại khóa khác nhau nào lên mỗi rương (mỗi loại nhiều nhất một ổ trên một rương), kể cả không đặt khóa nào.

Sau đó, Bob mua một tập hợp chìa khóa bất kỳ từ Alice (có thể không mua chìa nào, cũng có thể mua tất cả $m$ loại) và mở tất cả những chiếc rương mà anh có thể mở. Bob có thể mở một chiếc rương nếu sở hữu chìa khóa cho tất cả các ổ khóa trên rương đó; một rương không có ổ khóa nào thì Bob luôn mở được.

Lợi nhuận của Bob bằng tổng số xu trong các rương đã mở trừ tổng số xu dùng để mua chìa khóa. Nếu lợi nhuận của Bob lớn hơn $0$ thì Bob thắng; ngược lại (lợi nhuận bằng $0$ hoặc âm), Alice thắng.

Yêu cầu: Alice muốn đặt ổ khóa sao cho với mọi cách mua chìa khóa của Bob, lợi nhuận của Bob luôn không dương. Hãy xác định Alice có thể làm được điều đó hay không, và nếu có thì tổng số USD nhỏ nhất Alice cần dùng để đặt ổ khóa là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,m$ $(1\le n,m\le 6)$, lần lượt là số rương kho báu và số loại chìa khóa.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 4)$, là số xu trong các rương.
• Dòng thứ ba chứa $m$ số nguyên $b_1,b_2,\dots ,b_m$ $(1\le b_j\le 4)$, là giá bán các loại chìa khóa.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên. Số thứ $j$ của dòng thứ $i$ là $c_{i,j}$ $(1\le c_{i,j}\le {10}^7)$, chi phí đặt ổ khóa loại $j$ lên rương $i$.

Dữ liệu ra

Nếu Alice không thể đảm bảo chiến thắng (dù đặt ổ khóa thế nào, Bob luôn có cách mua chìa khóa để thu được lợi nhuận dương) thì in ra $-1$. Ngược lại, in ra số USD nhỏ nhất Alice cần dùng để đặt ổ khóa sao cho Bob không thể thu được lợi nhuận dương.

Ràng buộc

• $1\le n,m\le 6$.
• $1\le a_i\le 4$, $1\le b_j\le 4$.
• $1\le c_{i,j}\le {10}^7$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n,m,a_i,b_j\le 2$; $c_{i,j}\le {10}^3$.
• Subtask 2 ($30\%$ số điểm): $n,m,a_i,b_j\le 4$; $c_{i,j}\le {10}^5$.
• Subtask 3 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ