1387: 进化树

在生物学中，树可以用来表示物种之间的进化关系，这样的树称为进化树。在进化树中，每个叶子结点代表一个物种，如果每一条边都被赋予一个适当的权值，那么两个叶子结点之间的最短距离就可以表示相应的两个物种之间的差异程度。
生物学家Lee的一项重要工作就是根据实验得到的物种间差异程度数据构造出进化树，从而了解物种的进化过程。但是手工做这项工作实在太慢，他邀请你编写程序帮他完成。
Lee选择了n个物种，并从1到n进行编号，然后他对每两个物种进行比较，得到他们的差异程序值，并记录在一个n*n的差异程序表M中。在M中，第i行第j列的数据M[i,j]表示物种i和物种j之间的差异程度。Lee还总结出了关于进化树的几条规律：
（1） 进化树有且只有n个叶子，第i个叶子对应物种i。
（2） 每条边上的权值都是非负整数。
（3） M[i,j]就是进化树上叶子i和叶子j之间的最短距离，满足：M[i,i]=0, M[i,j]=M[j,i],而且满足三角不等式：对任意的i,j,k,总有M[i,j]+M[j,k]≥M[i,k]。
例如，对于下图的进化树，可以得到相应的差异程度表如下。

一棵进化树 对应的差异程度表

定义进化树的规模为该树所有边的权值之和。Lee发现，对同一个差异程度表M，所对应的进化树的规模总是固定的。换句话说，如果两棵进化树的规模不相等，那么它们各自对应的差异程度表也会有所不同。
现在你的任务就是编写程序，对于给定的差异程度表M，求出对应的进化树规模。

5
5 9 12 8
8 11 7
5 1
4

15