Flow Shop

A workshop builds custom swathers, the machines used to cut grain. Every swather goes through the same sequence of stages: a cutting bar is mounted, a grain belt is installed, a reel is fitted. The parts are customized for each buyer, so the same stage can take a different amount of time on different swathers.

$N$ swathers have been ordered and the manufacturing process has $M$ stages. Every swather passes through the stages in the same order, from stage 1 to stage $M$.

Stage $j$ takes $P_{i,j}$ units of time on swather $i$. The workers at a stage handle one swather at a time and never interrupt a job once they have started it. At time 0 all $N$ orders are waiting at stage 1. Whenever the workers at stage $j$ are idle and at least one swather is waiting there, they take the waiting swather with the smallest label; the swathers are labelled 1 to $N$. Stage $j$ can start on a swather only after stage $j-1$ has finished that same swather.

Determine the time at which each swather is completed.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 1000$), the number of swathers and the number of stages. Each of the next $N$ lines contains $M$ integers. The $j$-th integer on the $i$-th line is $P_{i,j}$ ($1 \le P_{i,j} \le 10^6$).

Print one line with $N$ integers $T_1\ T_2\ \dots\ T_N$, separated by single spaces, where $T_i$ is the time at which stage $M$ is completed for swather $i$.