Cho bảng số nguyên không âm kích thước nxn, hãy tính tổng các ô nằm trên đường chéo chính hoặc đường chéo phụ hoặc nằm ở biên.

Input

Dòng đầu gồm số n (1 ≤ n ≤ 1000)

Dòng thứ i (1 ≤ i ≤ n) trong n dòng sau chứa n số nguyên ~a_i, 1, a_i, 2, ..., a_i, n (a_i, j ≤ 10^9)~

Output

Gồm một dòng duy nhất là đán án cần tìm

Example

Sample Input

6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Sample Output

28