Farmer John muốn chụp một bức ảnh đàn bò đang gặm cỏ để treo lên tường. Đồng cỏ được biểu diễn bằng một lưới \(N\) hàng và \(N\) cột gồm các ô vuông, giống một bàn cờ \(N\times N\), với \(2\le N\le 1000\). Trong bức ảnh trước, đàn bò tụ lại quá đông ở một vùng. Lần này, ông muốn chúng được phân bố đều trên đồng cỏ và đặt ra các quy tắc sau:

• Không có hai con bò nào ở cùng một ô.
• Mọi lưới con \(2\times2\), có tổng cộng \((N-1)\times(N-1)\) lưới như vậy, phải chứa đúng 2 con bò.

Ví dụ, cách đặt sau hợp lệ:

CCC
...
CCC

Cách đặt sau không hợp lệ vì vùng \(2\times2\) chứa ô góc dưới bên phải chỉ có 1 con bò:

C.C
.C.
C..

Không có ràng buộc nào khác. Có thể giả sử Farmer John có vô hạn bò.

Farmer John muốn một số ô có bò hơn các ô khác. Cụ thể, khi đặt một con bò vào ô \((i,j)\), vẻ đẹp của bức ảnh tăng thêm \(a_{ij}\) đơn vị (\(0\le a_{ij}\le 1000\)). Hãy xác định tổng vẻ đẹp lớn nhất của một cách đặt bò hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\), tính từ trên xuống, là \(a_{ij}\).

Dữ liệu ra

In một số nguyên là vẻ đẹp lớn nhất có thể của bức ảnh.

Phân nhóm

• Các test 2-4 thỏa mãn \(N\le 4\).
• Các test 5-10 thỏa mãn \(N\le 10\).
• Các test 11-20 thỏa mãn \(N\le 1000\).

Ví dụ

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

22

CC..
..CC
CC..
..CC

Nguồn

USACO 2021 January Contest, Silver - Spaced Out: https://usaco.org/index.php?page=viewproblem2&cpid=1088

Tác giả: Hankai Zhang và Danny Mittal.