AT_past201912_g 組分け

有 $n$ 个人，编号 $1$ 到 $n$。现在要把他们分成**至多**三组。 对于每个满足 $1\le i\lt j\le n$ 的整数对 $(i,j)$，都会有一个整数 $a_{i,j}$ 表示 $i$ 和 $j$ 被分在一组时产生的“幸福指数”。若出现一个人独立成组的情况，那么他所产生的“幸福指数”为 $0$。 请求出“幸福指数”的最大和。

第一行：一个整数 $n$。 第二行至第 $n$ 行：第 $(i+1)$ 行第 $(j-1)$ 列输入整数 $a_{i,j}$。

一行一个整数，“幸福指数”最大和。

#### 样例 #1 说明 让 $1,2,3$ 一组，$4,5$ 一组，$6$ 一组，则“幸福指数”最大和为 $a_{1,2}+a_{1,3}+a_{2,3}+a_{4,5}=10+10+10+10=40$。 #### 样例 #2 说明 所有员工在同一组里。 #### 数据规模与约定 $2\le n\le 10$，$-10^6\le a_{i,j}\le 10^6$。