Maximizing Domino Sum on a 3‐Column Board

You are given an N×3 board with an integer written in each cell. In addition, you are given K dominoes each of size 1×2.

A domino can cover any two adjacent cells (either horizontally or vertically). Each domino, when placed, collects the sum of the numbers in the two cells it covers. The domino pieces cannot overlap. You are allowed to use at most K dominoes. Your task is to choose some placements of dominoes in order to maximize the total sum of the numbers covered by the dominoes.

The placement of dominoes is not required to cover the whole board. If placing a domino results in a negative contribution, it is allowed to leave cells uncovered.

Note: All formulas are rendered in LaTeX. For example, the board dimensions are given by \(N\times 3\) and a domino has size \(1\times2\).

inputFormat

The first line contains two integers \(N\) and \(K\) (the number of rows and the maximum number of dominoes available) separated by a space.

Then follow \(N\) lines, each containing 3 integers. The \(j\)-th integer in the \(i\)-th line represents the number written in the cell at row \(i\) (1-indexed) and column \(j\) (1-indexed).

outputFormat

Output a single integer, the maximum sum of the numbers covered by at most \(K\) dominoes.

sample

2 2
1 2 3
4 5 6

18