14741474 SUSTech Online Judge
Problem 1474 --Hexagon Cost

1474: Hexagon Cost

Time Limit: 2 Sec  Memory Limit: 1024 MB
Submit: 588  Solved: 195
[Submit][Status][Web Board]

Description

There a big hexagon, the side length is n, so there are \(3n^2+3n+1\) points, and \(9n^2+3n\) edges. Each point has a weight.

We define the weight of each edge as the multiplying result of the weight of two endpoints in it. Please find out the minimum cost to connect these \(3n^2+3n+1\) points.


Input

The first line contains an integer n \((1\leq n\leq 200)\), indicating the edge length of the hexagon. 

The next \(2n+1\) lines, line i contains \(2n+1-|i-n-1|\) integers w \((1\leq w\leq 10^6)\), indicating the weight of each node.

Output

Output the minimum cost in one line.


Sample Input

1
2 2
2 1 2
2 2

Sample Output

12

HINT

Source

 

[Submit][Status]