#include <bits/stdc++.h>
struct student {
  long int t;
  long int x;
  long int tout;
};
bool cmp_by_time(student a, student b) { return (a.t < b.t); }
bool cmp_by_coord(student a, student b) { return (a.x < b.x); }
using namespace std;
int main() {
  long int systime = 0;
  int stno, cap;
  cin >> stno >> cap;
  vector<student> students(stno);
  int i;
  for (i = 0; i < stno; i++) cin >> students[i].t >> students[i].x;
  vector<student>::iterator bus_begin = students.begin();
  while (bus_begin != students.end()) {
    vector<student>::iterator bus_end = bus_begin + cap - 1;
    if (bus_end >= students.end()) bus_end = students.end() - 1;
    if ((*bus_end).t > systime) systime = (*bus_end).t;
    sort(bus_begin, bus_end + 1, cmp_by_coord);
    vector<student>::iterator it;
    long int prevx;
    for (it = bus_begin, prevx = 0; it <= bus_end; it++) {
      long int currx = it->x;
      long int dx = currx - prevx;
      systime += dx;
      prevx = currx;
      int k = 0;
      while ((it->x == currx) && (it <= bus_end)) {
        k++;
        it->tout = systime;
        it++;
      }
      systime += 1 + (k / 2);
      it--;
    }
    bus_begin = bus_end + 1;
    systime += prevx;
  }
  sort(students.begin(), students.end(), cmp_by_time);
  vector<student>::iterator pri;
  for (pri = students.begin(); pri != students.end(); pri++)
    cout << pri->tout << " ";
  return 0;
}
