这是dp题吗
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一个由 n 行构成的数字三角形。第 i 行共有 2i-1 个整数，整体形状如下图所示（以 n=3 为例）：



\hspace{15pt}从顶点（第一行唯一的数字）出发，依次向下移动恰好 n-1 次直到抵达最后一行。
\hspace{15pt}假设当前位于第 i 行第 j 列：
{\hspace{20pt}}_\texttt{1.}\,可以向正下方移动至第 (i+1) 行第 j 列；
{\hspace{20pt}}_\texttt{2.}\,可以向左下方移动至第 (i+1) 行第 (j-1) 列；
{\hspace{20pt}}_\texttt{3.}\,可以向右下方移动至第 (i+1) 行第 (j+1) 列。

\hspace{15pt}每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为 l，向右下方移动的次数记为 r。我们需要满足


\left|l-r\right|\leqq k



\hspace{15pt}请你选择一条合法路径，使得获得数值之和最大，并输出该最大值。

输入描述:

\hspace{15pt}在一行上输入两个整数 n,k\left(1\leqq n\leqq 300;\ 0\leqq k\leqq n\right)，分别表示数字三角形的行数与允许的移动差。 
\hspace{15pt}此后 n 行，第 i 行输入 2i-1 个整数 

a_{i,1},a_{i,2},\dots ,a_{i,2i-1}\left(-2\times10^9\leqq a_{i,j}\leqq 2\times10^9\right)

\hspace{15pt}共计 \displaystyle\sum_{i=1}^{n}(2i-1)=n^2 个整数。

输出描述:

\hspace{15pt}输出一个整数，表示满足条件的路径可以取得的最大数值之和。
示例1

输入

复制 
3 1
1
2 3 4
5 6 7 8 9

输出

复制 
13

说明

\hspace{15pt}在该样例中，可选取的最大路径为 
\hspace{23pt}\bullet\,第 1 行：取 1； 
\hspace{23pt}\bullet\,第 2 行：向右下方移动，取 4； 
\hspace{23pt}\bullet\,第 3 行：向正下方移动，取 8。 
\hspace{15pt}总和为 1+4+8=13，且 \left|l-r\right|=1\leqq 1。
示例2

输入

复制 
3 0
1
2 3 4
5 6 7 8 9

输出

复制 
12