Số đặc biệt

Bối cảnh

Cho một bảng số kích thước \(N\times N\). Một ô số được gọi là đặc biệt nếu nó là giá trị lớn nhất trên đường chéo đi qua ô đó song song với đường chéo chính, đồng thời cũng là giá trị nhỏ nhất trên đường chéo đi qua ô đó song song với đường chéo phụ của bảng.

Yêu cầu

Yêu cầu: Hãy tính tổng tất cả các ô số đặc biệt.

Input

Dòng thứ nhất chứa số nguyên dương \(N\) (có giá trị không quá \(1000\));

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên (có giá trị tuyệt đối không quá \(10^9\)). Trong đó số thứ \(j\) của dòng thứ \(i\) thể hiện giá trị của ô có tọa độ \((i, j)\) trên bảng.

Output

Ghi ra một số nguyên duy nhất là tổng giá trị của tất cả các ô số đặc biệt, hoặc ghi ra \(0\) nếu không có ô số nào thỏa mãn.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

4
9 7 5 3
2 7 9 6
1 9 8 7
4 7 7 4

Output

18

Giải thích ví dụ

Các số ở các ô \((1, 1), (1, 4), (2, 4)\) là các số đặc biệt.

Thông tin học tập

• Buổi: B11
• Concepts: 2D arrays, row/column/diagonal traversal
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second
• Memory limit: 128 MB
• Point: 25