Paint walls

2

1 votes
Arrays, Implementation, Math Basic, Basics of Implementation, Basic Programming
Problem

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

  • First line: A single integer T denoting the number of test cases
  • For each test case:
    • First line: Three integers n, m, and k
    • Next n lines contains m space-separated numbers denoting the cost of repainting any cells

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

1T31n, m, k10000aij100000 for all i from [1, n] and for all j from [1, m]

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

 

TestCase-2

No possible way to print a 2X5 grid as the dimension of matrix is 3X3.

 

Editor Image

?