Hide

Problem D
Flow Shop

/problems/flowshop/file/statement/en/img-0001.jpg
Photo by ken figlioli cc by-sa 2.0
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 $P_{i,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.

Input

There is only one test case in each file. It begins with a single line containing $N$ and $M$ ($1 \leq N,M \leq 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 $P_{i,j}$, giving the amount of time it will take for the workers at stage $j$ to complete swather $i$ ($1 \leq P_{i,j} \leq 10^6$).

Output

Output a single line containing $N$ integers $T_1~ T_2~ \ldots ~ T_ n$ with a single space between consecutive integers. These should be such that stage $M$ for swather $i$ is completed at time $T_ i$.

Sample Input 1 Sample Output 1
2 3
1 2 3
3 2 1
6 7
Sample Input 2 Sample Output 2
3 2
3 1
4 7
2 5
4 14 19

Please log in to submit a solution to this problem

Log in