三倍经验

题目描述

数字金字塔由 $n$ 行整数组成,第 $i(1\le i\le n)$ 行有 $i$ 个数字,一个示例如下。 ```text 7 3 9 8 1 0 2 7 4 4 4 5 2 6 5 ``` 现在你在金字塔的顶部(第一行),你希望走到金字塔的底部(第 $n$ 行),每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友,你可以选择金字塔中的不多于 $k$ 个数字让他们成为原来的 $3$ 倍。 你会收集你路上经过的所有位置上的数字,最后的得分即为收集的数字之和,求最大得分。

输入输出格式

输入格式


第一行输入两个整数 $n,k$,表示数字金字塔的行数和乘 $3$ 的数字个数最大值; 接下来 $n$ 行,其中的第 $i$ 行有 $i$ 个以空格隔开的整数依次表示数字金字塔第 $i$ 行的数字 $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$。

输出格式


一行一个整数,表示最大得分。

输入输出样例

输入样例 #1

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

输出样例 #1

75

说明

对于 $30\%$ 的数据,满足 $k\le n\le 6$,并且对于任意 $1\le i\le n$,$1\le j\le i$ 满足 $0\le a_{i,j}\le 100$; 对于 $100\%$ 的数据,满足 $1\le n\le100$,$0\le k\le \dfrac{n(n+1)}{2}$,且对于任意 $1\le i\le n$,$1\le j\le i$ 满足 $|a_{i,j}|\le 10^9$。