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, 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 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 đó.

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, Alice thắng.

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. Đồng thời, Alice muốn tổng số USD dùng để đặt ổ khóa là nhỏ nhất.

Input

• 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~.

Output

Nếu Alice không thể đảm bảo chiến thắng thì in ~-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.

Scoring

Sample Input 1

2 3
3 3
1 1 4
10 20 100
20 15 80

Sample Output 1

205

Sample Input 2

2 3
3 4
1 1 4
10 20 100
20 15 80

Sample Output 2

-1