该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3016 [USACO11FEB] The Triangle S

题目描述

有一个边长 $n$ 行的等边三角形 $a_{i,j}$ ，从中选择边长至少为 $k$ 至多为 $2k$ 的相似等边三角形，使得所选等边三角形的平均值最大。

比如样例可以有这些选择方法：

                                                   /\
    / \         / \        / \         / \        /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   ---------  ----------  
  整个三角形      左下        上          右下       中间倒立
                      

输入格式

第一行两个整数 $n \ k \ (1 \le n \le 700, 1 \le k \le 20 , 1 \le k \le n)$

下来给出等边三角形的每个数 $a_{i,j} \ ( |a_{i,j}| \le 10^9)$

输出格式

一行一个整数，表示最大的平均值。

输入输出样例 #1

输入 #1

3 2 
5 
-8 4 
2 -3 6

输出 #1

2