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.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

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

Dữ liệu đầu ra

Ghi ra một số nguyên duy nhất là kết quả cần tìm.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1

INPUT

2
1 2
3 4

OUTPUT

3

Giải thích: Có ~1~ cách cắt.

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: ~3~.

Ví dụ 2

INPUT

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

OUTPUT

4

Giải thích: Có ~4~ cách cắt:

Trong các cách cắt, cách cắt thứ ~1~ có 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: ~4~.