题目描述

给定 $n$ 个点及任意两点之间的距离，设第 $i$ 个点与第 $j$ 个点之间的距离为 $d_{i,j}$。

请你从中选出 $n-1$ 条边，使得这 $n$ 个点连通成一棵树，且任意两点之间的点对距离之和最小。

输入格式

输入第一行，一个正整数 $n$ 接下来 $n-1$行中：第 $i$ 行 共 $n-i$ 个数，其中第 $i$ 行 第 $j$ 个数字表示 $i$ 号点与 $i+j$ 号点之间的距离。

输出格式

输出共一行，表示所求最小点对之和。

4
2 6 4
1 5
8

23

数据范围

• 对于 $30\%$ 的数据，$1\leq n \leq 4$
• 对于 $60\%$ 的数据，$1\leq n \leq 10$
• 对于 $100\%$ 的数据，$1\leq n,\leq 15$ ，$1 \leq d_{i,j} \leq 10^9$