Flower Path

On Arbor Day, April 5, 2017, Jina decided to plant flowers instead of trees in the flower bed in front of the Hi-Tech Building, so that she could walk along a path of flowers every day on her way to school.

Jina's flower seeds bloom exactly one year after they are planted, so she can walk the flower path starting from Arbor Day of the next year.

Jina has only three seeds. She wants all three flowers to survive and be in full bloom one year later.

The flower bed is an $N \times N$ grid, and Jina can plant a seed in any one of the cells from $(1,1)$ to $(N,N)$. A seed is planted in one cell as in figure (a), and when it blooms one year later it takes the shape in figure (b). A bloomed flower occupies 5 cells: the cell where the seed was planted (the stamen) and the cells directly above, below, left, and right of it (the petals).

There is one thing to be careful about. If, after blooming, a petal or stamen of one flower shares a cell with a petal or stamen of another flower, both flowers die. Also, if any petal extends outside the flower bed, that flower dies.

Figure (c) shows three flowers that bloomed normally, and figure (d) shows two flowers that died.

The rental price of the flower bed in front of the Hi-Tech Building differs for each cell of the grid. Jina wants to make all three seeds bloom while renting the flower bed at the lowest possible price.

The flower bed must be rented according to the shape of the bloomed flowers, so Jina has to rent 5 cells of land for each flower.

Jina does not have much money. Help her find the minimum cost needed to plant the flowers.

The first line contains $N$ ($6 \le N \le 10$), the side length of the flower bed.

Each of the next $N$ lines contains $N$ space-separated integers $G$ ($0 \le G \le 200$), the rental price of each cell of the flower bed.

Print the minimum cost needed to make all three flowers bloom.