#include <bits/stdc++.h>
using namespace std;
int n, m;
int csiz;
long long int heap[555555];
int qt[555555];
int qb[555555];
long long int ans[555555];
char ch;
int ret;
int read() {
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    ;
  for (ret = 0; ch >= '0' && ch <= '9'; ch = getchar())
    ret = ret * 10 + (ch & 15);
  return ret;
}
void pop() {
  int i;
  heap[1] = heap[csiz];
  heap[csiz--] = 0;
  for (i = 2; i <= csiz; i <<= 1) {
    if (i < csiz && heap[i + 1] < heap[i]) i++;
    if (heap[i] > heap[i >> 1]) break;
    swap(heap[i], heap[i >> 1]);
  }
}
void push(long long int g) {
  int i;
  heap[++csiz] = g;
  for (i = csiz; i > 1; i >>= 1) {
    if (heap[i] > heap[i >> 1]) break;
    swap(heap[i], heap[i >> 1]);
  }
}
int main() {
  int i, u, v, h, t;
  long long int g;
  n = read();
  m = read();
  csiz = 0;
  h = 0;
  t = 0;
  for (i = 1; i <= n; i++) {
    u = read();
    v = read();
    while (csiz != 0 && heap[1] < u) {
      g = heap[1];
      pop();
      if (h < t) {
        g += qt[h];
        ans[qb[h++]] = g;
        push(g);
      }
    }
    if (csiz < m) {
      ans[i] = u + v;
      push(u + v);
    } else {
      qt[t] = v;
      qb[t++] = i;
    }
  }
  while (h < t) {
    g = heap[1] + qt[h];
    ans[qb[h++]] = g;
    pop();
    push(g);
  }
  for (i = 1; i <= n; i++) printf("%I64d\n", ans[i]);
  return 0;
}
