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 sang 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_{ij}\). 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 cùng cột hoặc trên cùng đường chéo.

Yêu cầu: Gọ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.

Input

• 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\)).

Output

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

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(k \le 3\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 2
1 0 2
0 0 2
0 2 0

4