Description

A triangle of size $m$ consists of $m$ rows, and row $i$ contains $i$ elements.
Also, these rows must be arranged in the shape of an equilateral triangle.
For example, the following is a triangle with $m = 4$.

Each triangle also contains sub-triangles.
For example, the triangle above contains:

• $10$ triangles of size $1$.
• $6$ triangles of size $2$.
• $3$ triangles of size $3$.

Note that each triangle is also a sub-triangle of itself.
Now you are given a triangle of size $n$. For every sub-triangle of size $k$, find the sum of the maximum value among the numbers inside that sub-triangle.

Input Format

The first line contains two integers $n, k$, representing the size of the triangle and the required size of the sub-triangles.
The next $n$ lines describe the triangle: line $i$ contains $i$ integers.

Output Format

Output one integer: the sum, over all sub-triangles of size $k$, of the maximum value inside each sub-triangle.

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

23

Hint

Constraints

• Subtask 1 (25 pts): $n \le 1000$.
• Subtask 2 (75 pts): no special constraints.

For $100\%$ of the data, $1 \le k \le n \le 3000$, and $0 \le$ each number in the triangle $\le 10^9$.

Notes

Translated from CCC 2019 Senior T5 Triangle: The Data Structure.
Translator: @一只书虫仔.

Translated by ChatGPT 5