The Arrangement :
Difficulty Level : Hard
Submissions : 3063
Asked In :
Marks :10
: 18 | : 24
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 \times 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 atleast one valid arrangement of tiles always exists under given constrains.
Input
The first line contains $$$2$$$ integers $$$n,k(1 \leq n,k \leq 1000)$$$. The next $$$n$$$ lines contains $$$3$$$ integers each, the grid $$$(-10^6 \leq a_{i,j} \leq 10^6)$$$.
Output
Output a single integer - the maximum sum.
Example
Input
5 3 2 1 -1 1 3 2 0 2 3 2 1 1 3 3 0
Output
16
