Description

A number pyramid has $n$ rows of integers. The $i$-th row ($1 \le i \le n$) has $i$ numbers. One example is as follows.

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

Now you start at the top of the pyramid (the first row) and want to reach the bottom (the $n$-th row). At each step, you can move to the number down-left or down-right of your current position. Also, as a powerful kid, you may choose at most $k$ numbers in the pyramid and make them $3$ times their original value.

You will collect all numbers along your path. Your final score is the sum of the collected numbers. Find the maximum possible score.

Input Format

The first line contains two integers $n,k$, the number of rows in the number pyramid and the maximum count of numbers that can be multiplied by $3$.
Then follow $n$ lines. The $i$-th of them contains $i$ space-separated integers, which are the numbers in the $i$-th row of the pyramid: $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$.

Output Format

Output a single integer, the maximum score.

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

75

Hint

Constraints:
For $30\%$ of the testdata, $k \le n \le 6$, and for any $1 \le i \le n$, $1 \le j \le i$ it holds that $0 \le a_{i,j} \le 100$.
For $100\%$ of the testdata, $1 \le n \le 100$, $0 \le k \le \dfrac{n(n+1)}{2}$, and for any $1 \le i \le n$, $1 \le j \le i$ it holds that $|a_{i,j}| \le 10^9$.

Translated by ChatGPT 5