Art Union

题意翻译

有 $n$ 个画家和 $m$ 个画，每个画家手里都有一个不同的颜色，每幅画都需要这 $n$ 个画家涂上这 $m$ 个颜色，每个画的上色顺序必须是 $1\to n$ 的顺序，而每个画家也必须按照 $1\to m$ 的顺序画不同的画。也就是说，若一个画的前一种颜色没画好，后面颜色的画家就算提前画好前面的画了也只能等着前面所有颜色的画家都把这幅画画好了才能继续画。 已知第 $j$ 个画家画第 $i$ 幅画需要的时间是 $t_{i,j}$，问每幅画都是什么时候被所有画家画好，分别给出答案。

题目描述

A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of $ n $ painters who decided to organize their work as follows. Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these $ n $ colors. Adding the $ j $ -th color to the $ i $ -th picture takes the $ j $ -th painter $ t_{ij} $ units of time. Order is important everywhere, so the painters' work is ordered by the following rules: - Each picture is first painted by the first painter, then by the second one, and so on. That is, after the $ j $ -th painter finishes working on the picture, it must go to the $ (j+1) $ -th painter (if $ j<n $ ); - each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on; - each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest; - as soon as the $ j $ -th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter. Given that the painters start working at time 0, find for each picture the time when it is ready for sale.

输入输出格式

输入格式

The first line of the input contains integers $ m,n $ ( $ 1<=m<=50000,1<=n<=5 $ ), where $ m $ is the number of pictures and $ n $ is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains $ n $ integers $ t_{i1},t_{i2},...,t_{in} $ ( $ 1<=t_{ij}<=1000 $ ), where $ t_{ij} $ is the time the $ j $ -th painter needs to work on the $ i $ -th picture.

输出格式

Print the sequence of $ m $ integers $ r_{1},r_{2},...,r_{m} $ , where $ r_{i} $ is the moment when the $ n $ -th painter stopped working on the $ i $ -th picture.

输入输出样例

输入样例 #1

5 1
1
2
3
4
5

输出样例 #1

1 3 6 10 15 

输入样例 #2

4 2
2 5
3 1
5 3
10 1

输出样例 #2

7 8 13 21