[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$ 的三角形。 ![](https://cdn.luogu.com.cn/upload/image_hosting/fdut4hrs.png) 每个三角形还包含子三角形。 比如说上面这个三角形,包含: - $10$ 个大小为 $1$ 的三角形。 - $6$ 个大小为 $2$ 的三角形。 - $3$ 个大小为 $3$ 的三角形。 注意,每个三角形都是自身的子三角形。 现在给定一个大小为 $n$ 的三角形,求对于每个大小为 $k$ 的子三角形,子三角形内几个数的最大值的和。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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)。