1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <queue>
5 using namespace std;
6 typedef long long LL;
7 struct node{
8 int a;
9 int b;
10 LL num;
11 bool operator < (const node other)const{
12 return num > other.num;
13 }
14 };
15
16 priority_queue<node> pq;
17
18 LL A[1001][1001], t[1001];
19
20
21 int main(){
22 int m, n;
23 node temp;
24 cin >> m >> n;
25 for(int i = 0; i < m; ++ i){
26 for(int j = 0; j < n; ++ j){
27 cin >> A[i][j];
28 }
29 }
30
31 for(int i = 0; i < m; ++ i){
32 sort(A[i], A[i] + n);
33 }
34 for(int i = 1; i < m; ++ i){
35 for(int j = 0; j < n; ++ j){
36 temp.a = j;
37 temp.b = 0;
38 temp.num = A[i-1][j] + A[i][0];
39 pq.push(temp);
40 }
41 for(int j = 0; j < n; ++ j){
42 temp = pq.top();
43 pq.pop();
44 t[j] = temp.num;
45 if(temp.b != n - 1){
46 temp.b++;
47 temp.num = A[i - 1][temp.a] + A[i][temp.b];
48 pq.push(temp);
49 }
50 }
51 for(int j = 0; j < n; ++ j){
52 A[i][j] = t[j];
53 }
54 //pq.clear();
55 while(!pq.empty()){
56 pq.pop();
57 }
58 }
59 cout << t[0];
60 for(int i = 1; i < n; ++ i){
61 cout << " " << t[i];
62 }
63 return 0;
64 }
