Trên bàn cờ kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sáng phải. Ô nằm giao ở hàng \(i\) \((1 \le i \le n)\), cột \(j\) \((1 \le j \le n)\) được gọi là ô \((i,j)\), ô này có trọng số là \(w_{i,j}\). Cần đặt đúng \(k\) quân hậu lên bàn cờ để không có hai quân hậu nào chiếu nhau. Nhắc lại, hai quân hậu chiếu nhau nếu chúng được đặt trên cùng hàng hoặc trên cùng cột hoặc trên cùng đường chéo.

Yêu cầu

• Sọi \(s\) là tổng trọng số các ô có quân hậu đặt, tìm cách đặt để \(s\) là lớn nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(n,k\) \((k \le n \le 8)\)
• Dòng thứ \(i\) \((1 \le i \le n)\) trong \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên không âm mô tả trọng số của bảng (các số không vượt quá \(10^6\))

Dữ liệu ra

• Gồm một dòng chứa một số là tổng \(s\) lớn nhất đạt được.

Input 1

3 2
1 0 2
0 0 2
0 2 0

Output 1

4

Ràng buộc

• Subtask \(1\) (30%): \(k=1\)
• Subtask \(2\) (30%): \(k \le 3\)
• Subtask \(3\) (40%): không có ràng buộc nào thêm