题目描述

大 $H$ 举办了一个大型锦标赛。锦标赛由若干场比赛组成，并且有很多的选手。每场的参赛人数为 $n$。这 $n$ 个人参加比赛之后都会获得一个排名，排名是 $1$ 到 $n$ 的整数，并且这些排名两两不同。

如今，$HPL$ 决赛举办在即，共筛选出了 $n$ 名选手参加，编号为 $1\sim n$。

$i$ 号选手在之前的赛事中排名小于等于 $j$ 的比赛有 $c_{i,j}$ 次，每个选手的最后的得分会根据 $c_{i,j}$ 给出。根据定义，保证有 $c_{i,j}\le c_{i,j+1}$。

注：不一定满足每人的总场次相同，不一定满足每个排名的总人次相同。你也不需要关心在决赛之前的比赛具体的信息。

决赛打 $k$ 场，这 $k$ 场排名未知，但所有情况都有可能出现。每场都会将排名算入表现，最后得到 $c'_{i,j}$。

最终选手 $i$ 的得分为 $s_i=\max_{1\le j\le n}(c'_{i,j}-j)$（$s_i$ 可能为负数）。比赛的精彩值为所有选手得分之和 $\sum_{i=1}^{n}s_i$。

你想知道精彩值最大可能为多少。

输入格式

第一行两个数 $n,k$。

接下来 $n$ 行每行 $n$ 个数，第 $i$ 行第 $j$ 个数为 $c_{i,j}$。

输出格式

第一行输出一个数，表示最大可能的精彩值。

样例 1 输入

3 1
0 1 3
1 1 2
1 2 2

样例 1 输出

3

样例 1 解释

让 $2$ 号获得第一名，$3$ 号获得第二名，$1$ 号获得第三名。

新的表现分 $c'_{i,j}$ 变为：

0 1 4
2 2 3
1 3 3

有 $s_1=c'_{1,3}-3=1$，$s_2=c'_{2,1}-1=1$，$s_3=c'_{3,2}-2=1$。

样例 2 输入

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

样例 2 输出

10

说明与提示

对于所有数据：$2\le n\le 1600$，$1\le k\le 50$，$0\le c_{i,j}\le 10^6$。