#include <bits/stdc++.h>
using namespace std;
typedef struct el_ {
  int t, p;
} el;
int n, m, t, p;
el v1[100100];
el v2[100100];
int ans[100100];
bool temt[100100];
int start, size, in, now, ant, cnt, basetime, lastunload;
bool cmp2(el a, el b) {
  if (a.p == b.p) return a.t < b.t;
  return a.p < b.p;
}
int main() {
  memset(temt, false, sizeof(temt));
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &t, &p);
    el in = {t, p};
    v1[i] = in;
    v2[i] = in;
    temt[t] = true;
  }
  start = size = now = 0;
  in = 0;
  while (1) {
    while (in < m and start + size < n) in++, size++;
    sort(v2 + start, v2 + start + size, cmp2);
    if (now < v1[start + size - 1].t) now = v1[start + size - 1].t;
    basetime = now;
    lastunload = 0;
    ant = v2[start].p;
    cnt = 0;
    for (int i = start; i < start + size; i++) {
      if (v2[i].p != ant) {
        now += 1 + cnt / 2;
        basetime = now;
        lastunload = 1 + cnt / 2;
        ant = v2[i].p;
        ans[v2[i].t] = basetime + v2[i].p;
        cnt = 1;
      } else {
        ans[v2[i].t] = basetime + v2[i].p;
        cnt++;
      }
    }
    if (cnt != 0) lastunload = 1 + cnt / 2;
    now = basetime + lastunload + v2[start + size - 1].p * 2;
    in = 0;
    start = start + size;
    size = 0;
    if (start >= n) break;
  }
  cnt = 1;
  for (int i = 0; i < 100010; i++, cnt++)
    if (temt[i]) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
