Description

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

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

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

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

Input Format

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

Output Format

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

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

23

Hint

数据规模与约定

• 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。
翻译者：@一只书虫仔。