在本题中，我们考虑所有边权均为正的加权无向图。 令 $D(G, i, j)$ 表示图 $G$ 中顶点 $i$ 和顶点 $j$ 之间的最短路径长度。 给定一个包含 $n$ 个顶点的完全加权无向图 $G$，顶点编号从 $1$ 到 $n$。在 $G$ 的所有生成树中，MDSST（最小距离和生成树）是指使得值 $S(T) = \sum_{1 \le i < j \le n} D(T, i, j)$ 最小的生成树 $T$。你的任务是找到 $G$ 的 MDSST 并输出 $S(T)$。

输入格式

第一行包含一个整数 $n$，表示图中的顶点数 ($2 \le n \le 15$)。接下来的 $n-1$ 行中，第 $i$ 行包含 $n-i$ 个由空格分隔的整数。该行中的第 $j$ 个整数表示顶点 $i$ 和顶点 $i+j$ 之间的边长。 所有边长均在 $1$ 到 $10^9$ 之间（含边界）。

输出格式

输出一行，包含一个整数：你找到的 MDSST 的 $S(T)$ 值。

样例

样例输入 1

4
3 2 1
5 6
7

样例输出 1

18