#include <bits/stdc++.h>
using namespace std;
struct _ {
  _() { ios_base::sync_with_stdio(0); }
} _;
template <class A, class B>
ostream &operator<<(ostream &o, pair<A, B> t) {
  o << "(" << t.first << ", " << t.second << ")";
  return o;
}
template <class T>
string tostring(T first, int len = 0, char c = '0') {
  stringstream ss;
  ss << first;
  string r = ss.str();
  if (r.length() < len) r = string(len - r.length(), c) + r;
  return r;
}
template <class T>
void PV(T a, T b, int n = 0, int w = 0, string s = " ") {
  int c = 0;
  while (a != b) {
    cout << tostring(*a++, w, ' ');
    if (a != b && (n == 0 || ++c % n))
      cout << s;
    else
      cout << "\n";
    cout.flush();
  }
}
template <class T>
inline bool chmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
inline bool chmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
const long long linf = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = int(1e9) + 7;
const int N = 511111;
int n, k;
long long s[N];
long long t[N];
priority_queue<pair<long long, int>> server;
queue<int> Q;
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> s[i] >> t[i];
  vector<long long> res(n, 0);
  long long curTime = s[0];
  int i = 0;
  while (1) {
    while (i < n && curTime >= s[i]) {
      Q.push(i);
      i++;
    }
    if (server.size() > 0 && curTime == -server.top().first) {
      res[server.top().second] = curTime;
      server.pop();
    }
    if (server.size() < k && !Q.empty()) {
      long long finish = t[Q.front()] + curTime;
      server.push(make_pair(-finish, Q.front()));
      Q.pop();
    }
    long long nextTime = linf;
    if (server.size() > 0) chmin(nextTime, -server.top().first);
    if (Q.size() == 0 && i < n) chmin(nextTime, s[i]);
    curTime = nextTime;
    if (server.size() == 0 && Q.size() == 0 && i == n) break;
  }
  for (long long i : res) cout << i << "\n";
  return 0;
}
