#include <bits/stdc++.h>
using namespace std;
const int maxN = 100000 + 6;
const int maxX = 10000 + 6;
int t[maxN], x[maxN];
int cnt[maxX];
int lst[maxN], lstSize;
int w[maxN];
int beg[maxX];
int nxt[maxN];
int num[maxN];
int numSize;
int main() {
  memset(beg, -1, sizeof(beg));
  int n, m, i, t1, j, k;
  scanf("%d%d", &n, &m);
  for (i = 0; i < (int)(n); ++i) {
    scanf("%d%d", &t[i], &x[i]);
  }
  i = 0;
  t1 = 0;
  while (i < n) {
    lstSize = 0;
    numSize = 0;
    for (j = 0; j < m && i < n; ++j, ++i) {
      if (cnt[x[i]]++ == 0) lst[lstSize++] = x[i];
      nxt[numSize] = beg[x[i]];
      num[numSize] = i;
      beg[x[i]] = numSize;
      ++numSize;
    }
    sort(lst, lst + lstSize);
    ((t1) = max((t1), (t[i - 1])));
    for (j = 0; j < (int)(lstSize); ++j) {
      t1 += lst[j] - (j ? lst[j - 1] : 0);
      for (k = beg[lst[j]]; k != -1; k = nxt[k]) w[num[k]] = t1;
      t1 += 1 + (cnt[lst[j]] >> 1);
      cnt[lst[j]] = 0;
      beg[lst[j]] = -1;
    }
    t1 += lst[lstSize - 1];
  }
  for (i = 0; i < (int)(n); ++i) printf("%d%c", w[i], " \n"[i == n - 1]);
  return 0;
}
