该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

众所周知，数字三角形是 $OI$ 入门三万题之首，每位竞赛选手都做过它。

现在我们对这道经典题做了点小小的修改，但保留了一部分题目本来的味道。

现在你有一个大小为 $n$ 的由数字组成的三角形，你现在在最上方 $(1,1)$ 处。

每次你可以选择往正下或者往右下，即可以从 $(i,j)$ 走到 $(i+1,j)$ 或者 $(i+1,j+1)$ 处。

除此之外，你有 $k$ 次机会可以往正上或者左上走（当然你不能走出三角形），即可以从 $(i,j)$ 走到 $(i-1,j)$ 或者 $(i-1,j-1)$ 处。

问走到最后一行时，路上的数字之和最大是多少，同一个位置多次经过算多次。

注意：你没有必要把 $k$ 次机会都用完，且走到最后一行后如果机会没用完则仍然可以往回走。

输入格式

从 triangle.in 文件中读取数据

第一行两个整数 $n,k$。

接下来 $n$ 行，其中的第 $i$ 行有 $i$ 个整数，描述数字三角形。

输出格式

将数据输出到 triangle.out 文件中

输出一个整数表示答案

4 2
-1
2 3
-4 -5 -6
7 8 9 10

14

4 0
-1
2 3
-4 -5 -6
7 8 9 10

6

样例输入输出3

见 triangle3.in 与 triangle3.out

数据规模与约定

• 测试点 $1-2$ 满足 $1 \leq n \leq 5, 0 \leq k \leq 5$ 。

• 测试点 $3-4$ 满足 $1 \leq n \leq 500, k = 0$。

• 测试点 $5-6$ 满足 $1 \leq n \leq 500, k = 1$。

• 测试点 $7-8$ 满足 $1 \leq n \leq 100, 0 \leq k \leq 100$。

• 测试点 $9-10$ 满足 $1 \leq n \leq 500, 0 \leq k \leq 500$。

• 对于所有测试点，保证数字三角形内的每个数字的绝对值在 $2 \times 10^6$ 内。