Path on a board X13208

Statement

html

Consider an n × n board, where n is odd. From each cell, we can move to any of its (at most) four horizontally or vertically adjacent cells. For each cell, we have to pay a certain positive cost when we go through it. Compute the minimum cost of going from the center of the board to any cell on its periphery.

Input

Input consists of several cases, each with n, followed by an n × n matrix. You can assume that n is an odd number between 1 and 499, and that all costs are integer numbers between 1 and 1000.

Output

For every case, print the minimum cost to go from the middle of the board to any cell on the edge of the board.

Public test cases

Input

1
42

3
1 2 3
4 5 6
7 8 9

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

Output

42
7
136

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++