#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
const int maxt = 10001;
int n, m;
int t[maxn];
int x[maxn];
int ans[maxn];
vector<pair<int, int> > a;
int main(void) {
  scanf("%d %d", &n, &m);
  for (int j = 0; j < n; j++) scanf("%d %d", &t[j], &x[j]);
  int curtime = 0, curv = 0, i = 0;
  while (i < n) {
    while (i < n && curv < m)
      curtime = max(curtime, t[i]), a.push_back(make_pair(x[i], i)), i++,
      curv++;
    sort(a.begin(), a.end());
    int last = 0;
    for (int j = 0; j < (int)(a.size()); j++) {
      int end = j + 1;
      while (end < (int)(a.size()) && a[end].first == a[j].first) end++;
      curtime += (a[j].first - last), last = a[j].first;
      for (int k = j; k < end; k++) ans[a[k].second] = curtime;
      curtime += (end - j) / 2 + 1, curv -= (end - j);
      j = end - 1;
    }
    curtime += last;
    a.clear();
    cerr << "!!!" << endl;
  }
  for (int j = 0; j < n; j++) printf("%d ", ans[j]);
  return 0;
}
