C - 部門分け Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋くんのいる会社は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