CF523D Statistics of Recompressing Videos

一个为狗狗设计的社交网络 DogHouse（DH）有 $k$ 台专用服务器，用于重新压缩上传的可爱猫咪视频。每当一个视频被上传后，必须在一台（任意一台）服务器上被重新压缩，只有压缩完成后才能存入社交网络。 已知每台服务器压缩一分钟长的视频需要一秒钟。因此，任意服务器压缩一个时长 $m$ 分钟的视频需要 $m$ 秒。 已知共有 $n$ 个视频上传，每个视频在 $s_i$ 秒时被上传（这里的时间从所有服务器开始工作时刻算起）。所有视频上传的时间各不相同，并且这些视频按上传时间先后顺序给出。如果某个视频在 $s$ 秒上传，那么它的压缩可以立刻在这一时刻开始。如果所有服务器都忙，则视频会在队列中等待，按照上传顺序依次压缩。若在视频准备被压缩时，有服务器是空闲的，那么任意一台空闲服务器即可立即开始压缩该视频。 请计算每个视频完成压缩的时刻。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 5 \cdot 10^5$），分别表示视频数量和服务器数量。 接下来的 $n$ 行，每行为两个整数 $s_i, m_i$（$1 \leq s_i, m_i \leq 10^9$），表示第 $i$ 个视频的上传时刻（秒）和视频时长（分钟）。保证所有 $s_i$ 均不同，且按升序给出。

输出 $n$ 个整数 $e_1, e_2, \ldots, e_n$，其中 $e_i$ 表示第 $i$ 个视频完成压缩的时刻（以服务器工作开始为时间起点，单位为秒）。

由 ChatGPT 5 翻译