P1437 [HNOI2004] Knocking Bricks

无

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: ```cpp 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.

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 a single line containing one positive integer, the maximum total value of the knocked-out bricks.

Translated by ChatGPT 5