P3016 [USACO11FEB] The Triangle S

农夫 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$ 的三角形网格。这个问题的图像为: ```cpp / \ / 5 \ /-8 4\ /2 -3 6\ --------- ``` 她可以选择 $5$ 个子三角形的任意一个 ```cpp /\ / \ / \ / \ / \ /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 --------- ---------- 三角形 左下 顶部 右下 中间 整体 ``` 这是平均值最大的一组: ```cpp / \ / 5/\ /-8/ 4\ / 2/-3 6\ --------- ``` 这个子三角形的平均值为 $(4-3+6)\div3$，等于 $2.\dot3$（即 $2.333\dots$），所以答案为 $2$。 帮助 Bessie 求出她可获得金币的最大值。 **时简限制**: 2 秒。 **空间限制**: 32 MB。

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

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