Chênh lệch

Cho một bảng kích thước \(N \times N\), mỗi ô của bảng chứa một số nguyên. Thực hiện một đường cắt ngang và một đường cắt dọc chia bảng thành bốn phần là các hình chữ nhật hoặc hình vuông. Với mỗi cách cắt, giá trị của mỗi phần là tổng các số nguyên trong phần đó.

Yêu cầu: Hãy xác định chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất.

Input

Dữ liệu vào gồm:

• Dòng thứ nhất chứa số nguyên dương \(N\) (\(2 \le N \le 10^3\));

• \(N\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên có giá trị tuyệt đối không quá \(10^9\). Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

Ràng buộc:

• Subtask 1: Có ít nhất \(35\%\) số test có \(N \le 3\);

• Subtask 2: Có ít nhất \(14\%\) số test có \(N = 4\);

• Subtask 3: Có ít nhất \(20\%\) số test có \(4 < N \le 10^2\);

• Subtask 4: Số test còn lại không có ràng buộc gì thêm.

Output

In ra một số nguyên duy nhất là kết quả tìm được.

Example 1

Input:

2
1 2
3 4

Output:

3

Example 2

Input:

3
1 2 2
1 -1 4
2 2 -5

Output:

4

Note

Ví dụ 1: Chỉ có \(1\) cách cắt, phần nhỏ nhất có giá trị \(1\), phần lớn nhất có giá trị \(4\), chênh lệch là \(3\).

Ví dụ 2: Có \(4\) cách cắt, các chênh lệch lần lượt là \(4, 5, 10, 11\). Cách cắt thứ nhất có chênh lệch giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất là \(4\) (nhỏ nhất).