一道水题

Time Limit: 1000 ms

Memory Limit: 65535 KB

Description

王大锤给王小可出一道水题:给出m个数组,每个数组有n个非负数。现在从每个数组里面各选出一个数,相加得到一个和s。可想而知,一共有n^m种结果,但问题的关键是求出最小的n个s。面对这道水题,王小可顿时晕菜了,万能的程序员啊,帮帮他吧。

Input

第一行有一个整数T,代表T组数据,第二行有两个整数m,n(0<m<=100,0<n<=2000),接下来的m行,为m个含有n个元素的数组,数组里面的每个元素都不大于50000000。

Output

输出数据只有一行,包括n个最小的s,并且结果按升序排序,每两个s间由一个空格隔开,输出以回车换行符结束。

Sample Input

1
2 2
1 2
3 2

Sample Output

3 4

Hint

样例中m=2,n=2,所以有2个含有2个元素的数组 1 2 和 3 2,分别从这两个数组中各选出一个数 1 和 3,然后得到一个s=1+3,很容易地也得到剩下的s=1+2,s=2+3,s=2+2,然后从中选出最小的2个输出,即 3 4。

Source

“掌赢杯”南京理工大学第六届程序设计大赛网络预选赛

提交代码