#P1544. 三倍经验

三倍经验

题目描述

数字金字塔由 nn 行整数组成,第 i(1in)i(1\le i\le n) 行有 ii 个数字,一个示例如下。

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

现在你在金字塔的顶部(第一行),你希望走到金字塔的底部(第 nn 行),每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友,你可以选择金字塔中的不多于 kk 个数字让他们成为原来的 33 倍。

你会收集你路上经过的所有位置上的数字,最后的得分即为收集的数字之和,求最大得分。

输入格式

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

输出格式

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

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

提示

对于 30%30\% 的数据,满足 kn6k\le n\le 6,并且对于任意 1in1\le i\le n1ji1\le j\le i 满足 0ai,j1000\le a_{i,j}\le 100
对于 100%100\% 的数据,满足 1n1001\le n\le1000kn(n+1)20\le k\le \dfrac{n(n+1)}{2},且对于任意 1in1\le i\le n1ji1\le j\le i 满足 ai,j109|a_{i,j}|\le 10^9