Benita's Tiles: Maximum Sum Covered by Exactly K Dominoes

Problem Statement

Benita's Tiles Benita has a grid with `N` rows and exactly three columns. Lisa has written an integer value in every cell of the grid; each value is strictly smaller than `10^6` in absolute value. Benita has `K` tiles at her disposal. Every tile has dimensions `2 x 1` cells. She must place **all** `K` tiles on the grid, each tile laid either horizontally (covering two cells that are side by side in the same row) or vertically (covering two cells that are one above the other in the same column). Every tile therefore covers exactly two cells of the grid, tiles must lie entirely inside the grid, and no two tiles may overlap. The value covered by a placement is the sum of the numbers written in all cells covered by tiles. Benita wants that sum to be as large as possible. Note that a cell may hold a negative number, so covering more of the grid is not automatically better - but she still must place exactly `K` tiles. Print the largest total value that can be covered by placing exactly