#include <bits/stdc++.h>
using namespace std;
int capacity, students, inBus, student[100000], currentTime;
pair<int, int> bus[100000];
void goBus(int n, int time) {
  if (n == 0) return;
  currentTime = max(currentTime, time);
  sort(bus, bus + n);
  int prevPos = 0, thisStop = 0;
  for (int i = 0; i < n; i++) {
    if (bus[i].first == prevPos) {
      thisStop++;
    } else {
      currentTime += bus[i].first - prevPos;
      if (thisStop) currentTime += 1 + thisStop / 2;
      thisStop = 1;
      prevPos = bus[i].first;
    }
    student[bus[i].second] = currentTime;
  }
  currentTime += 1 + thisStop / 2 + prevPos;
}
int main() {
  cin >> students >> capacity;
  int time, pos;
  for (int i = 0; i < students; i++) {
    cin >> time >> pos;
    bus[inBus++] = make_pair(pos, i);
    if (inBus == capacity) {
      goBus(capacity, time);
      inBus = 0;
    }
  }
  goBus(inBus, time);
  for (int i = 0; i < students; i++) {
    cout << student[i] << " ";
  }
}
