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.
swathers have been
ordered and there are
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 and each stage
, it takes units of time to complete
stage for swather
. 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 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 to ). Note that the work on a stage
can only be started
after the work on the stage 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
and (), the number of
swathers and stages (respectively). Following this are
lines, each with
integers. The
’th integer of the
’th line is
, giving the
amount of time it will take for the workers at stage
to complete swather
().
Output
Output a single line containing integers with a
single space between consecutive integers. These should be such
that stage for swather
is completed at time
.
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
|