Grid Board

A grid has N rows and M columns, and each cell contains one positive integer. An integer K is given. K is at least 2, less than N, and less than M.

Choose R rows and C columns so that R + C = K. After removing every cell that belongs to a chosen row or a chosen column, consider the largest number among the remaining cells. Your goal is to make that largest number as small as possible.

Suppose N = 4 and M = 5, and the grid is as follows.

When K = 3, choosing rows 1 and 3 and column 4 leaves 5 as the largest number among the remaining cells.

Choosing row 3 and columns 3 and 4 also leaves 5 as the largest remaining number. However, no choice of rows and columns can make every remaining number smaller than 5.

Given the grid and the total number K of rows and columns to choose, write a program that minimizes the largest number among the cells not removed by the chosen rows and columns.

The first line contains two integers N and M, the size of the grid. N and M are each between 3 and 300, inclusive.

The second line contains K, the total number of rows and columns to choose. K is less than N and less than M.

The next N lines describe the grid from row 1 to row N. Each line contains M positive integers separated by spaces. Every number in the grid is between 1 and 500,000, inclusive.

On the first line, print the minimum possible value of the largest number among the cells that remain after choosing R rows and C columns with R + C = K.

On the second line, print R followed by the selected row numbers in increasing order. On the third line, print C followed by the selected column numbers in increasing order. If no row or no column is selected, print only 0 on that line.

Separate integers on the same line with one space. If there are multiple valid answers, print any one of them.