[CCC2019] Triangle: The Data Structure

在 Shuchong 的平行宇宙里，计算机学中的最重要的数据结构就是三角形。 注：因为原数据包太大，故这题缩减了一些数据，具体缩减的数据点如下： - Subtask 1：1 ~ 10 - Subtask 2：1 ~ 10 所以此题拥有的测试点为： - Subtask 1：11 ~ 26 - Subtask 2：11 ~ 24 若想测试本题没有的测试点请到 [此处](https://www.luogu.com.cn/problem/U120704) 测试。

大小为 $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](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) Senior T5 [Triangle: The Data Structure](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%201/seniorEF.pdf)。** 翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。