Description

农夫 FJ 颁给 Bessie 一个奇怪的奖项，以奖励她前几个月壮观的牛奶产量。他给她一个 $N$ 行的三角形网格（当然，三角形网格每行是 $1$ 到 $N$ 之间递增）。网格中第 $i$ 行有 $i$ 个数，数值为 $v_{i,j}$（$-10^9\le v_{i,j}\le 10^9$），其中 $j$ 为 $1\sim i$ 的数列。

Bessie 在这个三角形网格中选择了一个行数至少为 $K$ 的子三角形网格（$1 \le K \le N \le 700$，$1\le K\le 20$）。子三角形网格有可能和原来的三角形朝向相反，即子三角形网格朝向的较短行对应原来三角形的较长行。

Bessie 选择完子三角形网格后，FJ 会将子三角形中的所有数值求平均数，并抹除小数，然后给 Bessie 相对应的金币（若平均值为负，则从 Bessie 处拿相应的金币），Bessie 想要取得最大的利益（或最小的代价），请你帮她解决问题

例如，Bessie 被给了一个 $N=5,K=3$ 的三角形网格。这个问题的图像为:

    / \
   / 5 \
  /-8  4\
 /2 -3  6\
 ---------

她可以选择 $5$ 个子三角形的任意一个

                                                   /\
    / \         / \        / \         / \        /5 \       
   / 5 \       / \5\      / 5 \       / 5/\      /----\    
  /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\ 
 /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \ 
 ---------   ---------  -2  -3  6   ---------  ----------  
  三角形      左下          顶部         右下      中间
   整体                          

这是平均值最大的一组:

    / \
   / 5/\
  /-8/ 4\
 / 2/-3 6\
 ---------

这个子三角形的平均值为 $(4-3+6)\div3$，等于 $2.\dot3$（即 $2.333\dots$），所以答案为 $2$。

帮助 Bessie 求出她可获得金币的最大值。

时简限制: 2 秒。

空间限制: 32 MB。

Input Format

• 第一行两个用空格隔开的正整数 $N,K$。
• 第 $2\sim N$ 行，$i+1$ 行输入 $i$ 个用空格隔开的整数 $v_{i,j}$。

Output Format

• 一行，输出 Bessie 得到的金币最大值（可能为负）。

3 2 
5 
-8 4 
2 -3 6 

2