CF523D.Statistics of Recompressing Videos

A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.

We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.

We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.

For each video find the moment it stops being recompressed.

一个名为 DH（DogHouse，狗屋）的狗狗社交网络拥有 $k$ 台专用服务器，用于对上传的萌猫视频进行重新压缩。每段视频上传后，必须在其中一台（任意一台）服务器上完成重新压缩，之后才能保存到社交网络中。

已知每台服务器压缩 1 分钟视频片段需耗时 1 秒，因此任意一台服务器压缩一段 $m$ 分钟长的视频需耗时 $m$ 秒。

已知 $n$ 段视频各自上传至网络的时间（单位：秒，从所有服务器开始工作时刻起计）。所有视频均在互不相同的时刻上传，并按其上传顺序依次进行重新压缩。若某段视频于时刻 $s$ 上传，则其重新压缩可立即于该时刻 $s$ 开始。当所有服务器均处于忙碌状态时，部分视频需等待重新压缩。此时，一旦有服务器空闲，便立即开始处理队列中的下一段视频。等待重新压缩的视频按先进先出（FIFO）方式排队。若某段视频开始重新压缩时已有空闲服务器，则任一空闲服务器均可立即开始处理该视频。

对每一段视频，请计算其重新压缩完成的时刻。

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

Next n lines contain the descriptions of the videos as pairs of integers s__i, m__i (1 ≤ s__i, m__i ≤ 109), where s__i is the time in seconds when the i-th video appeared and m__i is its duration in minutes. It is guaranteed that all the s__i's are distinct and the videos are given in the chronological order of upload, that is in the order of increasing s__i.

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 5·10^5$），分别表示视频的数量和服务器的数量。

接下来的 $n$ 行，每行描述一个视频，包含一对整数 $s_i,\,m_i$（$1 ≤ s_i,\,m_i ≤ 10^9$），其中 $s_i$ 表示第 $i$ 个视频上传的时间（单位：秒），$m_i$ 表示该视频的时长（单位：分钟）。保证所有 $s_i$ 互不相同，且视频按上传时间升序给出，即按 $s_i$ 递增的顺序给出。

Print n numbers _e_1, _e_2, ..., e__n, where e__i is the time in seconds after the servers start working, when the i-th video will be recompressed.

输出 n 个数字 _e_₁, _e_₂, ..., e__n，其中 e__i 表示服务器开始工作后第 i 个视频被重新压缩的时刻（单位：秒）。