Description

In an $n$-row, $m$-column array of numbers, you must pick one number from each row (a total of $n$ numbers) and add them to get a sum. For the given array, please output the $k$ smallest picking methods by sum.

Input Format

The first line contains three numbers $n,m,k$. Lines $2\sim n+1$, each line contains $m$ positive integers.

Output Format

One line containing $k$ numbers, representing the $k$ smallest sums when picking one number from each row.

3 3 2
1 2 3
6 3 5
4 1 2

5 6

Hint

For $20\%$ of the testdata, $1\le n\le 8$. For $100\%$ of the testdata, $1\le n\le 800$, $1\le k\le m\le 800$. It is guaranteed that the final answer does not exceed $2^{31}-1$.

Translated by ChatGPT 5