Giám đốc công ty ABC cần giải quyết ~M~ công việc của công ty (các công việc được đánh số từ 1 tới ~M~). Hiện tại có ~N~ người thợ có thể thuê để làm cùng một lúc (các người thợ được đánh số từ 1 đến ~N~). Với công việc thứ ~i~, nếu thuê người thợ thứ ~j~ làm thì chi phí phải trả là ~a_{i,j}~.

Yêu cầu: Hãy tìm cách thuê các người thợ sao cho số công việc được giải quyết là nhiều nhất và chi phí phải trả là nhỏ nhất. Biết rằng mỗi người thợ chỉ làm đúng một công việc.

Input

• Dòng đầu ghi 2 số nguyên ~M, N~ (~1 \le M, N \le 30~)
• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ ghi ~N~ số nguyên dương ~a_{i,j}~ với ~i=1 \dots M, j=1 \dots N~ (~a_{i,j} \le 32000~)

Output

• Ghi ra một số duy nhất là tổng chi phí phải trả.

Sample Input 1

7 4
8 6 18 10
15 1 15 2
5 1 9 13
11 14 12 12
19 3 14 12
20 4 2 17
10 8 5 20

Sample Output 1

12