Problem Description

A company where Takahashi works consists of $ N $ employees. Between employees $ i $ and $ j $, there is a trust value $ w_{i,j} $. Due to the rapid growth of the company, it has been decided to divide the $ N $ employees into several departments. The score of a division into departments is defined as (the number of departments) * $ K $ - (the total trust value between pairs of employees belonging to different departments). Write a program to find the maximum score.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the maximum score in one line.

Sample Input and Output

Sample Input #1

3 3
0 1 5
1 0 1
5 1 0

Sample Output #1

4

Sample Input #2

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

Sample Output #2

11

Sample Input #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

Sample Output #3

12

Notes/Hints

Constraints

• $1 \leq N \leq 17$
• For $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$
• All inputs are integers.

Partial Points

• If you correctly solve all test cases where $N \leq 9$, you will be awarded 40 points as partial credit.
• If you correctly solve all test cases where $N \leq 15$, you will be awarded an additional 40 points as partial credit.

Sample Explanation 1

If we create one department with employees $ 1 $ and $ 3 $, and another department with employee $ 2 $, the number of departments is $ 2 $, and the total trust value between pairs of employees from different departments is $ 2 $. Thus, the score is $ 2*3-2=4 $. There is no way to get a score greater than $ 4 $.

见题面 Input 部分

见题面 Output 部分