← 返回题目列表

Codeforces · 523/D

D. 重新压缩视频的统计

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

名为 DH (DogHouse) 的狗狗社交网络有 k 个特殊服务器来重新压缩上传的可爱猫咪视频。每个视频上传后,应在一台(任意)服务器上重新压缩,然后才能保存在社交网络中。

我们知道每个服务器需要一秒钟来重新压缩一分钟的片段。因此,任何服务器需要花费 m 秒来重新压缩 m 分钟的视频。

我们知道 n 个视频中的每一个上传到网络的时间(从所有服务器开始工作的那一刻起以秒为单位)。所有视频都在不同的时间出现,并且按照出现的顺序重新压缩。如果某个视频在时间 s 出现,那么它的重新压缩可以在那一刻立即开始。当所有服务器都繁忙时,某些视频可以等待重新压缩。在这种情况下,一旦服务器可用,它就会立即开始重新压缩另一个视频。等待重新压缩的视频进入队列。如果在视频开始重新压缩时,某些服务器可用,则其中任何服务器都会开始重新压缩视频。

对于每个视频,找到它停止重新压缩的时刻。

输入

The first line of the input contains integers n and k (1 ≤ n, k ≤ 5 105) — the number of videos and servers, respectively.

接下来的 n 行包含以整数 si, mi (1 ≤ si, mi ≤ 109) 对形式表示的视频描述,其中 si 是第 i 个视频出现的时间(以秒为单位),mi 是其持续时间(以分钟为单位)。保证所有的si都是不同的,并且视频按照上传的时间顺序给出,即按照si递增的顺序。

输出

打印 n 个数字 e1, e2, ..., en,其中 ei 是服务器开始工作后的时间(以秒为单位),此时第 i 个视频将被重新压缩。

示例

输入 #1

3 2
1 5
2 5
3 5

输出 #1

6
7
11

输入 #2

6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3

输出 #2

1000000001
2000000001
3000000001
4000000001
5000000001
5000000004