AT_dp_u Grouping

有 $N$ 只兔子，每只兔子编号为 $1, 2, \ldots, N$。 对于每一对 $i, j$（$1 \leq i, j \leq N$），兔子 $i$ 和兔子 $j$ 的相性由整数 $a_{i, j}$ 给出。并且，对于每个 $i$（$1 \leq i \leq N$），有 $a_{i, i} = 0$，对于每对 $i, j$（$1 \leq i, j \leq N$），有 $a_{i, j} = a_{j, i}$。 太郎君想要将 $N$ 只兔子分成若干组。每只兔子必须恰好属于一个组。分组后，对于每一对 $i, j$（$1 \leq i < j \leq N$），如果兔子 $i$ 和兔子 $j$ 属于同一组，太郎君可以获得 $a_{i, j}$ 分。 请你求出太郎君能够获得的总分的最大值。

输入以以下格式从标准输入给出。 > $N$ > $a_{1, 1}\ a_{1, 2}\ \ldots\ a_{1, N}$ > $a_{2, 1}\ a_{2, 2}\ \ldots\ a_{2, N}$ > $\vdots$ > $a_{N, 1}\ a_{N, 2}\ \ldots\ a_{N, N}$

输出太郎君能够获得的总分的最大值。

## 限制条件 - 所有输入均为整数。 - $1 \leq N \leq 16$ - $|a_{i, j}| \leq 10^9$ - $a_{i, i} = 0$ - $a_{i, j} = a_{j, i}$ ## 样例解释 1 可以将兔子分为 $\{1, 3\}, \{2\}$ 两组。 ## 样例解释 2 可以将兔子分为 $\{1\}, \{2\}$ 两组。 ## 样例解释 3 可以将兔子分为 $\{1, 2, 3, 4\}$ 一组。答案可能超出 32 位整数范围。 由 ChatGPT 4.1 翻译