#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int maxn = 100007;
int n, m, T;
int top, k[10004], ans[maxn];
struct student {
  int t, x, i;
  void get(int l) {
    scanf("%d%d", &t, &x);
    i = l;
  }
  bool operator<(const student &b) const {
    if (t == b.t) return x < b.x;
    return t < b.t;
  }
} s[maxn], bus[maxn];
inline bool cmp(const student &a, const student &b) { return a.x < b.x; }
void geton(int &st) {
  top = 0;
  memset(k, 0, sizeof(k));
  for (int rest = m; st <= n && rest; st++, rest--) {
    bus[++top] = s[st];
    k[s[st].x]++;
    if (s[st].t > T) T = s[st].t;
  }
}
void getoff() {
  int t1 = 0, t2 = 0;
  sort(bus + 1, bus + top + 1, cmp);
  for (int i = 1; i <= top; i++) {
    if (bus[i].x != bus[i - 1].x) {
      T += t1;
      t1 = k[bus[i].x] / 2 + 1;
    }
    ans[bus[i].i] = bus[i].x + T;
  }
  T += bus[top].x * 2 + t1;
}
int main() {
  int st = 1, ti;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) s[i].get(i);
  sort(s + 1, s + n + 1);
  while (st <= n) {
    geton(st);
    getoff();
  }
  for (int i = 1; i <= n - 1; i++) printf("%d ", ans[i]);
  printf("%d\n", ans[n]);
  return 0;
}
