肯千网络公司最新推出了完全由偶像一对一对战构成的网络选秀节目。在该节目中，节目组邀请了 $n$ 位偶像，每天举办一场比赛，从仍然存活的偶像中选出两位进行一对一的PK，胜者将得到奖金，败者则将离开这个游戏，在之后不能再上台进行比赛。就这样进行 $n-1$ 场比赛，直到只剩下最后的偶像作为最终的冠军。 由于偶像之间的各种绯闻和恩恩怨怨，公司经过调查发现，如果第 $i$ 位偶像和第 $j$ 位偶像进行比赛，会给节目增加 $f(i,j)$ 的热度。 作为这个节目的运营，你可以任意挑选每天进行比赛的两名选手，甚至可以暗中操控比赛的胜负！你当然希望使得最终节目的总热度最大。那么，节目的总热度最多是多少呢？

第一行为一个整数 $n$ ($1 \leq n \leq 1000$)，表示偶像的个数。
接下来 $n - 1$ 行，第 $i$ 行有 $n - i$ 个数，第 $j$ 个数表示 $f(i, i + j)$，即第 $i$ 位偶像和第 $i + j$ 位偶像进行比赛增加的热度值 $(1 \leq f(i, i + j) \leq 10^8)$。

一个整数，为通过一路黑箱选出冠军的过程中节目的最大总热度。

对战安排及胜利情况如下：
$3 - 5$，热度 $12$，$3$获胜，
$1 - 2$，热度 $7$，$2$获胜，
$3 - 4$，热度 $8$，$3$获胜，
$2 - 3$，热度 $9$，冠军无论是谁都可以。
最后总热度 $12 + 7 + 8 + 9 = 36$。
可以证明，不存在更优的安排方案。