시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 3 3 2 100.000%

문제

Sean’s Swathers makes custom swathers (equipment used to harvest grain). All swathers go through the same basic stages in their construction: for example they all need to have a cutting bar, a grain belt, and a reel fitted. However, these components can be customized based on the buyer’s needs, so these various stages may take different amounts of time between different swathers.

N swathers have been ordered and there are M stages in the manufacturing process. The swathers will each go through the same sequence of stages.

In particular, the processing occurs as follows: For each swather i and each stage j, it takes Pi,j units of time to complete stage j for swather i. The workers at each stage may only work on one swather at a time. At the start of the day all swather orders are ready to be processed by the first stage. At any point in the process, if the workers at stage j are idle and there are swathers waiting to be processed at this stage then the workers will pick the swather that has the lowest label (they are labelled from 1 to N). Note that the work on a stage j can only be started after the work on the stage j − 1 is completed.

Determine the time each swather is completed.

입력

There is only one test case in each file. It begins with a single line containing N and M (1 ≤ N, M ≤ 1000), the number of swathers and stages (respectively). Following this are N lines, each with M integers. The j’th integer of the i’th line is Pi,j , giving the amount of time it will take for the workers at stage j to complete swather i (1 ≤ Pi,j ≤ 106).

출력

Output a single line containing N integers T1 T2 . . . Tn with a single space between consecutive integers. These should be such that stage M for swather i is completed at time Ti.

예제 입력 1

2 3
1 2 3
3 2 1

예제 출력 1

6 7

예제 입력 2

3 2
3 1
4 7
2 5

예제 출력 2

4 14 19

힌트