#include <bits/stdc++.h>
using namespace std;
int n, m, x, t;
vector<pair<int, int> > st;
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    q;
vector<int> ans;
int main() {
  cin >> n >> m;
  ans.assign(n + 1, 0);
  for (int(i) = (1); (i) <= (n); ++(i)) {
    cin >> t >> x;
    st.push_back(make_pair((t), (x)));
  }
  int curtime = 0;
  int curstud = 0;
  int total = 0;
  int bus = 0;
  int leave;
  while (curstud < n) {
    total = 0;
    while (total < m && curstud < n) {
      if (st[curstud].first - curtime > 0)
        curtime += st[curstud].first - curtime;
      q.push(make_pair((st[curstud].second), (curstud)));
      total++;
      curstud++;
    }
    bus = 0;
    while (!q.empty()) {
      leave = 1;
      pair<int, int> ss = q.top();
      q.pop();
      int x = ss.first;
      curtime += x - bus;
      bus = x;
      ans[ss.second] = curtime;
      while (!q.empty() && q.top().first == x) {
        ss = q.top();
        q.pop();
        ans[ss.second] = curtime;
        leave++;
      }
      curtime += 1 + leave / 2;
    }
    curtime += bus;
  }
  for (int(i) = (0); (i) <= (n - 1); ++(i)) cout << ans[i] << " ";
  return 0;
}
