#include <bits/stdc++.h>
using namespace std;
struct pii {
  int first, second;
  pii(){};
  pii(int f, int s) : first(f), second(s){};
  bool operator<(pii A) const { return first < A.first; }
};
int answers[100010];
int main() {
  int n, m, st = 0;
  cin >> n >> m;
  while (n > 0) {
    int lx = 0;
    pii stu[100010];
    for (int i = 0; i < min(n, m); i++) {
      int t, x;
      cin >> t >> x;
      stu[i + 1] = pii(x, i);
      st = max(t, st);
      lx = max(lx, x);
    }
    sort(stu + 1, stu + min(n, m) + 1);
    stu[0] = pii(0, -1);
    int lastpos = 0, lscore = st;
    for (int i = 1; i <= min(n, m); i++) {
      if (stu[i].first != stu[i - 1].first) {
        if (i > 1) lscore += 1 + (i - lastpos) / 2;
        lastpos = i;
        lscore += stu[i].first - stu[i - 1].first;
      }
      answers[stu[i].second] = lscore;
    }
    for (int i = 0; i < min(n, m); i++) cout << answers[i] << " ";
    lscore += 1 + (min(n, m) - lastpos + 1) / 2;
    n -= m;
    st = lscore + lx;
  }
  cout << endl;
}
