#include <bits/stdc++.h>
typedef struct {
  int t, x, n;
} person;
int cmpt(const void *n1, const void *n2) {
  person *nn1 = (person *)n1;
  person *nn2 = (person *)n2;
  return (nn1->t - nn2->t);
}
int cmpx(const void *n1, const void *n2) {
  person *nn1 = (person *)n1;
  person *nn2 = (person *)n2;
  return (nn1->x - nn2->x);
}
int main() {
  int n, m, ques = 0, buslen, end, quelen;
  unsigned long long res[100010], bustime = 0;
  person *que = (person *)malloc(sizeof(person) * 100010);
  scanf("%d", &n);
  scanf("%d", &m);
  quelen = n;
  for (int i = (0); i < (n); i++) {
    scanf("%d", &que[i].t);
    scanf("%d", &que[i].x);
    que[i].n = i;
  }
  que[n].t = que[n].x = que[n].n = -1;
  qsort((void *)que, n, sizeof(person), cmpt);
  while (quelen != 0) {
    end = (((quelen) < (m)) ? (quelen) : (m));
    buslen = end;
    if ((unsigned long long)que[end - 1].t > bustime) bustime = que[end - 1].t;
    qsort((void *)que, end, sizeof(person), cmpx);
    int lastx = 0, nowx, count;
    for (int i = (0); i < (buslen); i++) {
      nowx = que[i].x;
      count = 0;
      bustime += nowx - lastx;
      while (que[i].x == nowx && i < end) {
        res[que[i].n] = bustime;
        count++;
        i++;
      }
      i--;
      lastx = nowx;
      bustime += 1 + ((int)(count / 2));
    }
    bustime += que[end - 1].x;
    que += end;
    quelen -= end;
  }
  for (int i = (0); i < (n); i++) {
    printf("%I64u ", res[i]);
  }
  return 0;
}
