← 返回题目列表

AtCoder · arc056_c

C. 司

中文机器翻译题面 查看原题

問題文

高桥君的公司是 由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