Brick Cracker Pyramid

You are given a triangular arrangement of bricks. There are \(n\) layers. The top layer (layer 1) contains \(n\) bricks, the second layer contains \(n-1\) bricks, and so on, with the bottom layer having 1 brick. Each brick has a score associated with it. If you knock a brick, you obtain its score.

The bricks are arranged as follows (for example, when \(n=5\)):

14  15   4   3  23
 33  33  76   2
  2  13  11
   22  23
    31

The dependency rule is defined in terms of brick positions. Let \(a_{i,j}\) denote the score of the \(j\)th brick on the \(i\)th layer (\(1\le j\le n-i+1\)). To knock off brick \(a_{i,j}\):

• If \(i = 1\), you can knock it directly.
• If \(i > 1\), you can knock it only if you have already knocked off both bricks \(a_{i-1,j}\) and \(a_{i-1,j+1}\) in the previous layer.

You are allowed to knock off at most \(m\) bricks. Find the maximum total score you can obtain by choosing a valid set of bricks to knock off.

Note: A set of bricks is valid if for every brick in layer \(i>1\) that is knocked off, its two "parent" bricks in layer \(i-1\) (at positions \(j\) and \(j+1\)) are also knocked off. In other words, if you choose a brick in a lower level, then you must have chosen the two bricks above it. This naturally forces the knocked bricks to form one or more downward pyramids, each with a contiguous segment in the top layer.

A pyramid is defined by choosing a contiguous segment of bricks from the top row (layer 1). If the segment covers positions \(i\) to \(j\) (with \(1\le i\le j\le n\)), then you are allowed to extend this pyramid downward up to a height \(h\) (with \(1\le h\le j-i+1\)). The pyramid then includes bricks from layer 1 (positions \(i\) to \(j\)), layer 2 (positions \(i\) to \(j-1\)), layer 3 (positions \(i\) to \(j-2\)), ..., layer \(h\) (positions \(i\) to \(j-h+1\)). The total number of bricks used in such a pyramid is \[ C = \sum_{r=0}^{h-1} ((j-i+1)-r) = h\cdot (j-i+1)-\frac{h\cdot (h-1)}{2}. \] and the score is the sum of the values of all these bricks. You may select several (non overlapping) pyramids (choosing a pyramid of height 1 is equivalent to knocking off one brick from layer 1). It is also allowed to not knock off some bricks at all. The total number of knocked bricks (i.e. the sum of the sizes of the chosen pyramids) must not exceed \(m\).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of layers and the maximum number of bricks you can knock off, respectively).\

Then follow \(n\) lines. The \(i\)th line contains \(n-i+1\) integers representing the scores of the bricks in the \(i\)th layer.

For example, when \(n=5\), the input is:

5 5
14 15 4 3 23
33 33 76 2
2 13 11
22 23
31

outputFormat

Output a single integer, the maximum total score that can be obtained under the given constraints.

sample

5 5
14 15 4 3 23
33 33 76 2
2 13 11
22 23
31

123