### 问题描述 有 $n$ 个顶点的加权无向完全图，点的编号为 $1 \sim n$，连接编号 $i$ 和编号 $j$ 的边的权重为 $w[i][j]$。 请你选择一些边，并使得选择的边的权重之和尽可能大。 你选择的边必须满足以下条件：所选的边的端点是成对不同的，即一个端点不能出现在多条选择的边中。 ### 输入格式 第 $1$ 行输入一个整数表示 $n$。 第 $2$ 行到第 $n$ 行，每一行包括若干个整数。 其中第 $k(2\leq k\leq n)$ 行包括 $n-k+1$ 个整数，表示编号为 $k-1$ 的点与编号为 $k,k+1,…,n$ 的点连成的边的权重，即 $w[k-1][k] \sim w[k-1][n]$ 。 ### 输出格式 输出一个整数表示你选择的边的最大可能权重。 ### 样例输入 ```text 4 1 5 4 7 8 6 ``` ### 样例输出 ```text 13 ``` ### 说明 如果选择连接顶点 $1$ 和 $3$ 的边，以及连接顶点 $2$ 和 $4$ 的边，则边的总权重为 $5+8=13$。 可以证明，这是可实现的最大值。 ### 评测数据规模 保证对于所有测试数据有： $2 \leq n \leq 16,1\leq w[i][j]\leq10^9$ 。