3262. [CCC 2019]三角形

【题目描述】

大小为 $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

【数据规模与约定】

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