Company: Algo university_2june
Difficulty: medium
Maximum Grid Tile Sum Problem Description You have a grid with n rows and 3 columns. Each cell has a value written on it. You also have k tiles of dimensions 2 x 1. You need to place all the tiles on the grid vertically or horizontally such that no tiles overlap and the sum of values covered by the tiles is maximum. Find this maximum value. It is guaranteed that at least one valid arrangement of tiles always exists under given constraints. Input The first line contains 2 integers n , k . The next n lines contain 3 integers each, representing the grid. Output Output a single integer - the maximum sum. Examples Example 1: Input: 5 3 2 1 -1 1 3 2 0 2 3 2 1 1 3 3 0 Output: 16 Constraints 1 ≤ n, k ≤ 1000 -10 6 ≤ a i,j ≤ 10 6 (where a i,j is the value of a cell in the grid)