题目背景

在 Shuchong 的平行宇宙里，计算机学中的最重要的数据结构就是三角形。
注：因为原数据包太大，故这题缩减了一些数据，具体缩减的数据点如下：

• Subtask 1：1 ~ 10
• Subtask 2：1 ~ 10

所以此题拥有的测试点为：

• Subtask 1：11 ~ 26
• Subtask 2：11 ~ 24

若想测试本题没有的测试点请到 此处 测试。

题目描述

大小为 $m$ 的一个三角形由 $m$ 行组成，第 $i$ 行包含 $i$ 个元素。
并且，这些行必须排为等边三角形的形状。
比如说，以下是一个 $m=4$ 的三角形。

每个三角形还包含子三角形。
比如说上面这个三角形，包含：

• $10$ 个大小为 $1$ 的三角形。
• $6$ 个大小为 $2$ 的三角形。
• $3$ 个大小为 $3$ 的三角形。

注意，每个三角形都是自身的子三角形。
现在给定一个大小为 $n$ 的三角形，求对于每个大小为 $k$ 的子三角形，子三角形内几个数的最大值的和。

输入格式

第一行两个整数 $n,k$ 代表三角形的大小和要求的子三角形的大小。
接下来 $n$ 行第 $i$ 行有 $i$ 个整数代表这个三角形。

输出格式

一行一个整数代表对于每个大小为 $k$ 的子三角形，子三角形内几个数的最大值的和。

4 2
3
1 2
4 2 1
6 1 4 2

23

提示

数据规模与约定

• Subtask 1（25 pts）：$n \le 1000$。
• Subtask 2（75 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le k \le n \le 3000$，$0 \le$ 三角形内每个数 $\le 10^9$。

说明

翻译自 CCC 2019 Senior T5 Triangle: The Data Structure。
翻译者：@一只书虫仔。