← 返回题目列表

Codeforces · 416/B

B. 艺术联盟

中文机器翻译题面 查看原题

一个名为“Kalevich is Alive!”的知名艺术联盟生产艺术品(图片)。该工会由 n 位画家组成,他们决定按如下方式组织他们的工作。

每个画家仅使用分配给他的颜色。所有画家的颜色都是不同的。我们假设第一个画家使用颜色 1,第二个画家使用颜色 2,依此类推。每张图片将包含所有这n种颜色。将第 j 个颜色添加到第 i 张图片需要第 j 个画家 tij 单位的时间。

顺序在任何地方都很重要,因此画家的作品按以下规则排序:

- 每幅画首先由第一个画家绘制,然后由第二个画家绘制,依此类推。即第j个画家完成图片工作后,必须转到第(j + 1)个画家(如果j < n);
- 每个画家按某种顺序处理图片:首先,他画第一幅画,然后画第二幅画,依此类推;
- 每个画家最多可以同时处理一张图片。然而,画家们不需要任何时间休息,他们需要时间来休息。
- 一旦第 j 个画家完成了他在图片上的工作,该图片就立即可供下一个画家使用。

鉴于画家在时间 0 开始工作,找出每幅画准备出售的时间。

输入

输入的第一行包含整数 m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5),其中 m 是图片数量,n 是画家数量。然后按照图片的描述进行操作,每行一张。每行包含 n 个整数 ti1, ti2, ...,tin (1 ≤ tij ≤ 1000),其中 tij 是第 j 个画家处理第 i 张图片所需的时间。

输出

打印 m 个整数 r1, r2, ..., rm 的序列,其中 ri 是第 n 个画家停止绘制第 i 张图片的时刻。

示例

输入 #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