#include <bits/stdc++.h>
using namespace std;
const int MAXN = 101000;
map<int, vector<int> > quant;
int res[MAXN];
int main() {
  int n, m, back = 0, in_queue = 0, ctime;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int ct, cx;
    scanf("%d%d", &ct, &cx);
    quant[cx].push_back(i);
    in_queue++;
    if (in_queue == m || i == n - 1) {
      ctime = max(back, ct);
      int prevy = 0, cy;
      for (map<int, vector<int> >::iterator iter = quant.begin();
           iter != quant.end(); ++iter) {
        cy = iter->first;
        ctime += cy - prevy;
        const vector<int>& stud = iter->second;
        for (int snum = 0; snum < stud.size(); snum++) {
          res[stud[snum]] = ctime;
        }
        ctime += (1 + stud.size() / 2);
        prevy = cy;
      }
      back = ctime + cy;
      quant.clear();
      in_queue = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", res[i]);
  }
  printf("\n");
  return 0;
}
