1549: ACW_5135. 奶牛用餐

约翰的农场有 n 头奶牛，编号 1∼n。

每天奶牛们都要去食堂用餐。

食堂一共有 k 个座位，也就是说同一时间最多可以容纳 k 头奶牛同时用餐。

已知，第 i 头奶牛到达食堂的具体时刻为 si，用餐所需花费的时间为 ti。

保证 s1<s2<…<sn。

为了让奶牛们有序用餐，约翰制定了如下规则：

• 每头奶牛都必须由约翰安排座位用餐。
• 每头奶牛从到达食堂的那一刻起，即刻进入待安排状态。
• 任意时刻，只要存在空座位以及待安排奶牛，约翰就会即刻安排奶牛就座用餐。
• 如果某一时刻，空座位的数量少于待安排奶牛的数量，则优先安排编号更小的奶牛就座用餐。
• 每头奶牛用餐完毕的那一时刻都会被约翰立即轰走，即刻空出座位。

除了用餐花费时间以外，其它花费时间忽略不计。

请你计算并输出，每头奶牛用餐完毕的具体时刻。

第一行包含两个整数 n,k。

接下来 n 行，其中第 i 行包含两个整数 si,ti。

注意，输入保证 s1<s2<…<sn。

3 2
1 5
2 5
3 5

6
7
11