Triple Boosted Path in Number Pyramid

The problem consists of a number pyramid with \(n\) rows. The \(i\)-th row (1 \(\le\) \(i\) \(\le\) \(n\)) contains \(i\) integers. For example, a pyramid with 5 rows is given below:

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

You start at the top of the pyramid (the first row) and wish to reach the bottom (the \(n\)th row). From any position, you may only move to the number immediately to the left or right in the row directly below.

In addition, you are allowed to choose no more than \(k\) numbers in the pyramid and triple their value (i.e. replace a number \(a\) by \(3a\)). The score of a path is the sum of all numbers you collect along the path after applying any tripling operations. Your goal is to maximize this score.

Note: Any mathematical formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of rows in the pyramid and the maximum number of tripling operations allowed, respectively).

Then \(n\) lines follow. The \(i\)-th line contains \(i\) integers, representing the numbers in the \(i\)-th row of the pyramid.

outputFormat

Output a single integer: the maximum possible score achievable on a valid path from the top to the bottom of the pyramid.

sample

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

47