問題文
高桥君的公司是 由N员工组成。员工i和员工j之间的可靠性w_{i,j}已修复。 感谢你们,公司得以快速发展,N决定将人员分为几个部门。这里,划分得分为(划分数量)*K-(属于不同的部门2人与人之间的信任总量)。 编写一个程序来找出最高分。
制約
- 1 ≦ N ≦ 17
- i≠j 时, 除以 1 ≦ w_{i,j} ≦ 10^6
- w_{i,i} = 0
- w_{i,j}=w_{j,i}
- 1 ≦ K ≦ 10^6
- 所有输入均为整数 如果所有满足
部分点
- N ≦ 9 的测试用例都被正确回答,将给出部分分数。 如果所有满足40分被给予。
- N ≦ 15 的测试用例都被正确回答,则额外的分数将作为部分分数添加。 输出40分被给予。
入力
输入将以以下形式通过标准输入给出。
N K
w_{1,1} ... w_{1,N}
:
w_{N,1} ... w_{N,N}
出力
1行的最高分数。
入力例1
3 3 0 1 5 1 0 1 5 1 0
出力例1
4
社員1和 将其放在3可以访问第1两个部门,员工2可以访问第1如果您创建两个部门, 部门数量为2不同部门之间2人们的信任总量为2所以,2*3-2=4变为。 分数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