题目描述

有一个网站叫 DH，有 $n$ 个视频和 $k$ 个服务器。每个服务器可以同时压缩一个视频。多个服务器可以一起工作。

现在给定每个视频的长度 $m_i$ 和两两不等的上传时间 $s_i$（每个视频只有在上传了之后才可以压缩）输出每个视频开始压缩的时间，使得总时间最短。

输入格式

第一行两个整数 $n,k$，$1\le n,k\le 5\times 10^5$。

接下来 $n$ 行，每行两个整数 $s_i,m_i$，$1\le s_i,m_i\le 10^9$。以 $s_i$ 单调上升给出。

输出格式

输出 $n$ 行，表示每个视频开始压缩的时间。

3 2
1 5
2 5
3 5

6
7
11

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

1000000001
2000000001
3000000001
4000000001
5000000001
5000000004