Problem Statement

高橋くんのいる会社は$N$人の社員からなる。社員$i$と社員$j$の間には、信頼度$w_{i,j}$が定まっている。 おかげ様で会社はぐんぐん成長したため、$N$人をいくつかの部門に分けることになった。ここで、部門分けのスコアを、(部門の数)*$K$-(異なる部門に属する$2$人の間の信頼度の総和)と定める。 スコアの最大値を求めるプログラムを書いてください。

Constraints

• $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$点が与えられる。

Input

入力は以下の形式で標準入力から与えられる。

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

Output

$1$行目に、スコアの最大値を出力せよ。