题目描述

江桥正在编织手链！

共有 $n$ 颗珠子，若第 $i$ 颗珠子和第 $j$ 颗珠子相邻，则该手链的美观度增加 $a_{i,j}$。 保证 $a_{j,i} = a_{i,j}$ 且 $a_{i,i} = 0$。

江桥可以编制若干条手链，每条手链由一些珠子连接而成，但是必须满足下面所有条件：

$1$、所有珠子都要被编进手链中

$2$、每条手链至少包含 $k$ 颗珠子

为了继续提升美观度，在所有手链编制完毕后，江桥会把这些手链首尾相接组成若干个手环。当然，一条手链既可以自己首尾相接，也可以与其他手链连接，相接的珠子会增加手链的美观度。

注意，长度为 $1$ 的手环美观度为 $0$，长度为 $2$ 的手环中两颗珠子算相邻两次。所有珠子都要被编进某个手环。

江桥想知道，他能够编制的所有可能的一个或多个手环中，所有手环的美观度总和最大是多少。

输入格式

第一行，两个正整数 $n,k$。

接下来 $n$ 行每行 $n$ 个非负整数,第 $i$ 行第 $j$ 个非负整数表示 $a_{i,j}$。

输出格式

一个非负整数，表示答案。

8 2
0 6 9 4 2 4 0 4
6 0 7 7 3 3 7 4
9 7 0 7 0 9 10 1
4 7 7 0 8 0 6 10
2 3 0 8 0 3 8 7
4 3 9 0 3 0 6 5
0 7 10 6 8 6 0 9
4 4 1 10 7 5 9 0

66

样例解释

无

数据规模与约定

下发文件

下发文件分别对应子任务 $4$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $3 \leq n \leq 17,1 \leq k \leq n,0 \leq a_{i,j} \leq 10^6,a_{i,j} = a_{j,i},a_{i,i} = 0$。