시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

In this problem, we will consider weighted undirected graphs where all edges have positive weights.

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$ which consists of $n$ vertices numbered from $1$ to $n$. Among the spanning trees of $G$, the MDSST (Minimum Distance Sum Spanning Tree) is such $T$ for which the value $S(T) = \sum_{1 \leq i < j \leq n} D(T,i,j)$ is minimum. Your task is to find MDSST of $G$ and print $S(T)$.

입력

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 of this the line is the length of the edge between vertex $i$ and vertex $i+j$.

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

출력

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

예제 입력 1

4
3 2 1
5 6
7

예제 출력 1

18