SP20863 MINSUB - Largest Submatrix

You are given an matrix $M$ (consisting of nonnegative integers) and an integer $K$. For any submatrix of $M'$ of $M$ define $\min(M')$ to be the minimum value of all the entries of $M'$. Now your task is simple: find the maximum value of $\min(M')$ where $M'$ is a submatrix of $M$ of area at least $K$ (where the area of a submatrix is equal to the number of rows times the number of columns it has).

The first line contains a single integer $T$ ($T \le 10$) denoting the number of test cases, $T$ test cases follow. Each test case starts with a line containing three integers, $R$ ($R \le 1000$), $C$ ($C \le 1000$) and $K$ ($K \le R \times C$) which represent the number of rows, columns of the matrix and the parameter $K$. Then follow $R$ lines each containing $C$ nonnegative integers, representing the elements of the matrix $M$. Each element of $M$ is $\le 10^9$.

For each test case output two integers: the maximum value of $\min(M')$, where $M'$ is a submatrix of $M$ of area at least K, and the maximum area of a submatrix which attains the maximum value of $\min(M')$. Output a single space between the two integers.