A wall in your room can be considered as a two dimensional matrix of n rows and m columns.
Initally, the wall is painted white and repainting any cell (i, j) has a cost aij. You want to paint a HackerEarth logo of dimension two rows and k columns (2×K) in the minimum cost possible.The logo can be painted either horizontally or vertically. You are required to determine the minimum cost you must pay to get the wall painted.
If there is no possible way to get the wall painted, then print −1. Otherwise, print the minimum cost.
Note: The logo can be painted in form of 2×K or K×2 that provides you the minimum cost.
Input forrmat
Output format
For each test case, print the minimum cost to repaint the wall. If it is not possible to repaint a wall, then print −1.
Constraints
1≤T≤31≤n, m, k≤10000≤aij≤100000 for all i from [1, n] and for all j from [1, m]
TestCase-2
No possible way to print a 2X5 grid as the dimension of matrix is 3X3.