Description

In a trough, there are $n$ layers of bricks. The top layer has $n$ bricks, and each lower layer has one fewer brick. Each brick has a score; knocking out a brick yields its score, as shown below:

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

If you want to knock out the $j$-th brick in the $i$-th layer, then if $i=1$, you can knock it out directly; if $i>1$, you must first knock out the $j$-th and the $(j+1)$-th bricks in layer $i-1$.

You may knock out at most $m$ bricks. Find the maximum total score you can obtain.

Input Format

The first line contains two positive integers $n$ and $m$; then $n$ lines follow, describing the scores $a_{i,j}$ on these $n$ layers, where $0 \leq a_{i,j} \leq 100$.

For $100\%$ of the testdata, it holds that $1 \leq n \leq 50$, $1 \leq m \leq \frac{n \times (n+1)}{2}$.

Output Format

Output a single line containing one positive integer, the maximum total value of the knocked-out bricks.

4 5
2 2 3 4
8 2 7
2 3
49

19

Hint

Translated by ChatGPT 5