Giả sử giá trị của một ma trận là hiệu giữa tổng các số trên đường chéo chính với tổng các số trên đường chéo phụ. Cho ma trận A kích thước N × N, hãy tìm ma trận con của A sao cho ma trận con đó có giá trị lớn nhất.

Input

• Dòng đầu tiên: chứa số nguyên dương N (2 ≤ N ≤ 400).

• N dòng tiếp theo: mỗi dòng chứa N số nguyên trong khoảng [−1000, 1000] biểu diễn ma trận A.

Output

• Một số nguyên duy nhất là giá trị của ma trận con lớn nhất tìm được.

Sample

Input #1

3
1 2 3
4 5 6
7 8 9

Output #1

0

Problem source: Free Contest 56