K Smallest Sum Selection Methods

Given an integer matrix of size $$n \times m$$, you need to select one number from each row (i.e. choose $$n$$ numbers) and compute their sum. Your task is to output the selection methods that yield the smallest $$k$$ sums. A selection method is defined as the list of chosen numbers, in order of the rows. The results should be sorted primarily by the total sum in increasing order, and in case of ties, by the lexicographical order of the selected sequence.

Note: It is guaranteed that the matrix is small enough for a brute-force approach to pass.

inputFormat

The first line of input contains three integers $$n$$, $$m$$, and $$k$$ separated by spaces.

This is followed by $$n$$ lines, each containing $$m$$ integers representing the rows of the matrix.

outputFormat

Output exactly $$k$$ lines. Each line should represent a selection method in the following format:

sum: num1 num2 ... num_n

Here, sum is the total sum of the chosen numbers, and num1, num2, ... , num_n are the numbers selected from each row in order.

sample

2 2 3
2 3
1 4

3: 2 1
4: 3 1
6: 2 4