题目描述

我们需要将 $n$ 个物品分组，划分成多少小组都是可以的，每个小组至少有一件物品。如果第 $i$ 个物品和 第 $j$ 个物品分在一组，会产生 $w_{i,j}$ 的得分（$i<j$）。请找到一种分组方案，让得分达到最大。

注意一些物品分在一组内会产生负数的分数。

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n$ 行：在第 $i+1$ 行有 $i$ 个整数，表示 $a_{1,i}, a_{2,i}, \dots, a_{i-1,i}$

输出格式

• 单个整数：表示最大得分。

4
3 
4 5
6 7 8

33

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 8$
• 对于 $60\%$ 的数据，$1\leq n\leq 12$
• 对于 $100\%$ 的数据，$1\leq n\leq 16$，$-10^9 \leq a_{ij} \leq 10^9$