Computing MDSST

Time limit1sMemory limit512 MB

Summary

Given a complete weighted graph on at most 15 vertices, find the spanning tree whose sum of all pairwise shortest-path distances is smallest, and print that sum.

Level: Hard8 of 10
Topics: Graph, Minimum spanning tree, Brute force, Bit manipulation
Solved: No attempts yet

Problem

In this problem we consider weighted undirected graphs where every edge has positive weight.

Let $D(G,i,j)$ be the length of the shortest path in graph $G$ between vertex $i$ and vertex $j$ .

We are given a complete weighted undirected graph $G$ with $n$ vertices numbered from $1$ to $n$ . Among the spanning trees of $G$ , the MDSST (Minimum Distance Sum Spanning Tree) is the tree $T$ that minimizes $S(T) = \sum\_{1 \leq i < j \leq n} D(T,i,j)$ . Find the MDSST of $G$ and print $S(T)$ .

Input

The first line contains an integer $n$ , the number of vertices in the graph ( $2 \le n \le 15$ ). The $i$ -th of the following $n-1$ lines contains $n-i$ integers separated by spaces. The $j$ -th integer on this line is the length of the edge between vertex $i$ and vertex $i+j$ .

All lengths are between $1$ and $10^9$ , inclusive.

Output

On the first line, print one integer: the value $S(T)$ for the MDSST you found.

Examples1

Example 1
Input
```
4
3 2 1
5 6
7
```
Expected output
```
18
```