#include <bits/stdc++.h>
using namespace std;
struct student {
  int t, x, i;
};
int cmp(const void *a, const void *b) {
  const struct student *aa = (const struct student *)a,
                       *bb = (const struct student *)b;
  if (aa->x < bb->x) return -1;
  if (aa->x > bb->x) return 1;
  return 0;
}
int cmp2(const void *a, const void *b) {
  const struct student *aa = (const struct student *)a,
                       *bb = (const struct student *)b;
  if (aa->i < bb->i) return -1;
  if (aa->i > bb->i) return 1;
  return 0;
}
int main() {
  int n, m, c, i, j, t = 0, a, x;
  cin >> n >> m;
  struct student *bus = (struct student *)calloc(m, sizeof(*bus));
  c = n / m;
  for (i = 0; i < c; ++i) {
    for (j = 0; j < m; ++j) {
      cin >> bus[j].t >> bus[j].x;
      bus[j].i = j;
    }
    t = (bus[m - 1].t > t) ? bus[m - 1].t : t;
    qsort(bus, m, sizeof(*bus), cmp);
    j = 0;
    x = 0;
    while (j < m) {
      a = 1;
      t += bus[j].x - x;
      x = bus[j].x;
      bus[j].t = t;
      while (++j < m && bus[j - 1].x == bus[j].x) {
        bus[j].t = t;
        a++;
      }
      t += (1 + (a / 2));
    }
    t += bus[m - 1].x;
    qsort(bus, m, sizeof(*bus), cmp2);
    for (j = 0; j < m; ++j) {
      cout << bus[j].t << " ";
    }
  }
  if (!(c = n % m)) return 0;
  for (j = 0; j < c; ++j) {
    cin >> bus[j].t >> bus[j].x;
    bus[j].i = j;
  }
  t = (bus[c - 1].t > t) ? bus[c - 1].t : t;
  qsort(bus, c, sizeof(*bus), cmp);
  j = 0;
  x = 0;
  while (j < c) {
    a = 1;
    t += bus[j].x - x;
    x = bus[j].x;
    bus[j].t = t;
    while (++j < c && bus[j - 1].x == bus[j].x) {
      bus[j].t = t;
      a++;
    }
    t += (1 + (a / 2));
  }
  t += bus[c - 1].x;
  qsort(bus, c, sizeof(*bus), cmp2);
  for (j = 0; j < c; ++j) {
    cout << bus[j].t << " ";
  }
  return 0;
}
