#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
long long n, k, tmp, a, b;
long long s[1000050], m[1000050], t[1000050];
priority_queue<long long> q;
int main() {
  cin >> n >> k;
  for (int(i) = 1; (i) <= (k); (i)++) q.push(0);
  for (int(i) = 1; (i) <= (n); (i)++) {
    scanf("%d%d", &a, &b);
    tmp = q.top();
    q.pop();
    tmp = min(tmp, -a);
    printf("%I64d\n", b - tmp);
    q.push(tmp - b);
  }
  return 0;
}
