AT_arc056_c [ARC056C] 部門分け

高桥君所在的公司有 $N$ 名员工。员工 $i$ 和员工 $j$ 之间有一个信任度 $w_{i,j}$。由于公司业务蒸蒸日上，现在需要将 $N$ 名员工分成若干个部门。这里，部门划分的得分定义为（部门数）$\times K$ 减去（属于不同部门的两人之间的信任度总和）。请编写程序，求得分的最大值。

输入通过标准输入按以下格式给出。 > $N$ $K$ $w_{1,1}$ ... $w_{1,N}$ : $w_{N,1}$ ... $w_{N,N}$

输出第 $1$ 行，给出最大得分。

## 限制条件 - $1 \leq N \leq 17$ - 当 $i \neq j$ 时，$1 \leq w_{i,j} \leq 10^6$ - $w_{i,i} = 0$ - $w_{i,j} = w_{j,i}$ - $1 \leq K \leq 10^6$ - 所有输入均为整数 ## 部分得分 - 若能正确解决所有 $N \leq 9$ 的测试用例，可获得 $40$ 分。 - 若能正确解决所有 $N \leq 15$ 的测试用例，可额外获得 $40$ 分。 ## 样例解释 1 如果将员工 $1$ 和 $3$ 分为一个部门，员工 $2$ 单独为一个部门，则部门数为 $2$，不同部门之间的信任度总和为 $2$，因此得分为 $2 \times 3 - 2 = 4$。没有比得分 $4$ 更高的划分方法。 由 ChatGPT 4.1 翻译