#include <bits/stdc++.h>
using namespace std;
int drop[100010];
struct student {
  int t, x, id;
};
student S[100010];
struct sf {
  bool operator()(const int& a, const int& b) { return S[a].x > S[b].x; }
};
int main() {
  int N, M;
  cin >> N >> M;
  queue<int> Q;
  for (int i = 0; i < N; i++) {
    int t, x;
    cin >> t >> x;
    S[i].t = t;
    S[i].x = x;
    S[i].id = i;
    Q.push(i);
  }
  int t = 0;
  int x = 0;
  priority_queue<int, vector<int>, sf> B;
  while (!Q.empty()) {
    while (true) {
      int i = Q.front();
      Q.pop();
      if (S[i].t > t) t = S[i].t;
      B.push(i);
      if ((B.size() == M) || (Q.empty())) break;
    }
    int last = 0;
    int k = 0;
    while (!B.empty()) {
      int i = B.top();
      B.pop();
      if (S[i].x == last) {
        k++;
        drop[i] = t;
      } else {
        if (k > 0) {
          t += 1 + (int)((k / 2));
        }
        t += (S[i].x - last);
        last = S[i].x;
        drop[i] = t;
        k = 1;
      }
    }
    if (k > 0) {
      t += 1 + (int)((k / 2));
    }
    assert(last >= 0);
    t += last;
  }
  for (int i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << drop[i];
  }
  cout << endl;
}
