Hard Divide and Conquer > Dynamic Programming

You are playing a game with Alice. Before starting the game, Alice gives you a board with **N** rows and **M** columns. Each cell of the board ( there are N X M cells ) will have a number printed on it. Now Alice gives you P tile blocks, each tile block is **2 X 1** sized. You should put all the tile blocks on that given board. But your goal is to maximize the sum of those cell's number which are covered by the tile blocks. You started to think about the game and you found out that it will be quite hard to find the maximum sum if N and M is arbitrary number. As Alice is so kind, so she guarantees that M will always be 3 and permits you to rotate the tile blocks if you want. Input: ------ Input starts with an integer T (1<= T <= 10), denoting the number of test cases. each case contains the integer N (1 ≤ N ≤ 1000), the number of rows, and P (1 ≤ P ≤ 1000), the number of tile blocks will be given by Alice. Each of the following N lines contains three integers printed in the i'th row of the board. All numbers will be lesser than 10^9 by absolute value. Output: ------- For each case you should print the maximum sum achievable from that board if you put all the tile blocks efficiently. Sample Input ------------ 1 3 3 2 2 2 3 -3 -3 4 5 5 Sample Output ------------- 21 Hint ------------- You shouldn't cover the cells with negative value and one of the cell which have a value of 2

Ahmad Faiyaz