Problem D: Hexagon Cost

Problem D: Hexagon Cost

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


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.


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 the minimum cost in one line.

Sample Input

2 2
2 1 2
2 2

Sample Output