#include <bits/stdc++.h>
using namespace std;
int main() {
  int stud, vmar;
  cin >> stud >> vmar;
  int mar[vmar];
  int poryadok[10001];
  int count = 0;
  int lastnumber;
  if (vmar != 1)
    for (int b = 0; b < stud; b += vmar) {
      if (vmar > stud) vmar = stud;
      int max = 0;
      if (b + vmar > stud) vmar = stud - b;
      for (int c = 0; c < vmar; c++) {
        cin >> lastnumber >> mar[c];
        if (mar[c] > max) max = mar[c];
      }
      if (lastnumber > count) count = lastnumber;
      for (int d = 0; d <= max; d++) poryadok[d] = 0;
      for (int d = 0; d < vmar; d++) poryadok[mar[d]]++;
      int count3 = 0;
      for (int d = 0; d < vmar; d++) {
        int curcount = 0;
        for (int c = 0; c < mar[d]; c++) {
          if (poryadok[c] != 0) curcount = curcount + poryadok[c] / 2 + 1;
          curcount++;
        }
        if (mar[d] == max) count3 = count + curcount;
        cout << count + curcount << " ";
      }
      count = max + poryadok[max] / 2 + 1 + count3;
    }
  else {
    int r, y, count = 0;
    for (int b = 0; b < stud; b++) {
      cin >> r >> y;
      if (r > count) count = r;
      count += y;
      cout << count << " ";
      count += y + 1;
    }
  }
}
