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

        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 行的数字

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

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

luogu