#include <bits/stdc++.h>
using namespace std;
int i, j;
pair<int, int> p[111111];
int ans[111111];
int m, t, n, k, l, r, tp, z;
int main() {
  cin >> n >> m;
  i = 1;
  t = 0;
  while (i <= n) {
    for (j = 0; i + j <= n && j < m; j++) {
      cin >> k >> p[j].first;
      t = max(t, k);
      p[j].second = i + j;
    }
    sort(p, p + j);
    for (z = 0; z < j;) {
      t += p[z].first;
      if (z) t -= p[z - 1].first;
      int ii = z;
      while (ii < j && p[z].first == p[ii].first) {
        ans[p[ii].second] = t;
        ii++;
      }
      t += 1 + (ii - z) / 2;
      z = ii;
    }
    i += j;
    t += p[j - 1].first;
  }
  for (i = 1; i <= n; i++) printf("%d ", ans[i]);
}
