Cho một ma trận vuông kích thước ~n \times n~ với các phần tử là số nguyên. Hãy tìm một hình vuông con kích thước ~3 \times 3~ sao cho tổng các phần tử trong hình vuông đó là lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ — kích thước của ma trận.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên, biểu diễn các hàng của ma trận.

Output

In ra một số duy nhất là tổng lớn nhất của một hình vuông con kích thước ~3 \times 3~.

Ràng buộc

• ~3 \le n \le 555~
• ~-9999 \le A[i][j] \le 9999~ (với mọi ~0 \le i, j < n~)

Ví dụ

Ví dụ 1

Input:

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Output:

9

Giải thích:

Ma trận ~4 \times 4~ với tất cả phần tử bằng ~1~. Bất kỳ hình vuông con kích thước ~3 \times 3~ nào cũng có tổng bằng ~9~ (vì ~3 \times 3 = 9~ phần tử, mỗi phần tử bằng ~1~).

Ví dụ 2

Input:

3
1 2 3
4 5 6
7 8 9

Output:

45

Giải thích:

Ma trận là ~3 \times 3~, có chỉ một hình vuông con kích thước ~3 \times 3~ (chính ma trận). Tổng các phần tử: ~1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45~.

Ví dụ 3

Input:

5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Output:

153

Giải thích:

Ma trận là ~5 \times 5~. Có ~(5 - 2) \times (5 - 2) = 9~ hình vuông con kích thước ~3 \times 3~ khác nhau.

Hình vuông con có tổng lớn nhất nằm ở vị trí (~i = 2~, ~j = 2~) (0-indexed):

13 14 15
18 19 20
23 24 25

Tổng: ~13 + 14 + 15 + 18 + 19 + 20 + 23 + 24 + 25 = 153~.