#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int, int> a, pair<int, int> b) {
  if (a.first < b.first) return true;
  return false;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int> > a(m);
  vector<pair<int, int> > w(m);
  int time = 0;
  int pos = 0;
  for (int i = 0, pred = 0, left = n; i < n;) {
    time += pos;
    int t;
    int kol = min(left, m);
    for (; i < pred + kol; i++) {
      scanf("%d%d", &t, &a[i - pred].first);
      a[i - pred].second = i;
    }
    time = max(time, t);
    sort(a.begin(), a.begin() + kol, comp);
    int pr = 0;
    for (int j = 0; j < kol;) {
      time += a[j].first - pr;
      pr = a[j].first;
      int k = 1;
      for (j++; j < kol && a[j].first == a[j - 1].first; k++, j++)
        ;
      for (int tmp = j - 1; tmp >= j - k; tmp--) {
        w[tmp].second = time;
        w[tmp].first = a[tmp].second;
      }
      time += 1 + k / 2;
    }
    pred += kol;
    pos = a[kol - 1].first;
    left -= kol;
    sort(w.begin(), w.begin() + kol, comp);
    for (int j = 0; j < kol; j++) printf("%d ", w[j].second);
  }
  return 0;
}
