问题描述

高桥所在的公司由 $N$ 名员工组成。员工 $i$ 和员工 $j$ 之间有一个信任值 $w_{i,j}$。 由于公司不断发展壮大，需要将 $N$ 名员工分为若干个部门。定义部门分配的得分为 (部门数) $\times K$ - (属于不同部门的两人之间的信任值总和)。请编写程序求得最大得分。

约束条件

• $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$ 分。

输入

输入以以下格式从标准输入中给出。

$N$ $K$ $w_{1,1}$ ... $w_{1,N}$ : $w_{N,1}$ ... $w_{N,N}$

输出

输出一个整数，表示最大得分。

示例1

3 3
0 1 5
1 0 1
5 1 0

输出示例1

4

将员工 $1$ 和 $3$ 分在一个部门，员工 $2$ 分在一个部门，此时部门数为 $2$，不同部门之间的两人信任值总和为 $2$，所以得分为 $2 \times 3 - 2 = 4$。没有办法得到更大的得分。

示例2

4 8
0 2 3 5
2 0 1 2
3 1 0 8
5 2 8 0

输出示例2

11

示例3

5 10
0 10 1 2 1
10 0 1 2 1
1 1 0 6 7
2 2 6 0 8
1 1 7 8 0

输出示例3

12