#include <bits/stdc++.h>
using namespace std;
int N, M;
int ts[100001];
int xs[100001];
int res[100001];
int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) cin >> ts[i] >> xs[i];
  int prvBusTime = 0;
  int pos = 0;
  while (pos < N) {
    int curBusTime = prvBusTime;
    priority_queue<pair<int, int> > pq;
    for (int i = 0; i < M && pos < N; i++) {
      curBusTime = max(curBusTime, ts[pos]);
      pq.push(pair<int, int>(-xs[pos], pos));
      pos++;
    }
    int prvPlc = 0;
    while (pq.size()) {
      pair<int, int> p = pq.top();
      pq.pop();
      int curStop = -p.first;
      int cnt = 1;
      curBusTime += curStop - prvPlc;
      prvPlc = curStop;
      res[p.second] = curBusTime;
      while (pq.size()) {
        if (curStop == -pq.top().first) {
          cnt++;
          res[pq.top().second] = curBusTime;
          pq.pop();
        } else
          break;
      }
      curBusTime += 1 + cnt / 2;
    }
    curBusTime += prvPlc;
    prvBusTime = curBusTime;
  }
  for (int i = 0; i < N; i++) {
    cout << res[i];
    if (i == N - 1)
      cout << endl;
    else
      cout << " ";
  }
  return 0;
}
