Problem E: PIPI的存钱罐Ⅱ

Problem E: PIPI的存钱罐Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 7
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI目前有n个存钱罐,每个存钱罐有m枚硬币,每枚硬币都有其对应的面值。
现在PIPI准备从每个存钱罐中取出一枚硬币,请问所有取钱方案中,硬币面值之和前k小的方案是哪些?

Input

第一行三个正整数n,m,k,n<=50,m<=10000,k<=10000,数据保证一定合法。
接下来n行,每行m个正整数a[i][j],表示硬币对应的面值,a[i][j]<=10^9。

Output

输出k行,第i行表示取钱方案中第i小的面值和。

Sample Input

2 2 3
1 3
4 2

Sample Output

3
5
5

HINT

样例解释:
总共有4种取钱方案,分别是{1,4},{1,2},{3,4},{3,2},其面值和分别为{5,3,7,5}。
因此所有取钱方案中,硬币面值之和前3小的方案是{3,5,5}。