#include <bits/stdc++.h>
using namespace std;
pair<int, int> A[100010];
int times[100010];
int main() {
  int n, m;
  std::ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> A[i].first >> A[i].second;
  }
  int time = 0;
  int capa = 0;
  int last = 0;
  while (last < n) {
    while (capa < m && last + capa < n) {
      capa++;
    }
    set<pair<int, int> > dist;
    for (int i = last; i < last + capa; i++) {
      dist.insert(pair<int, int>(A[i].second, i));
    }
    last += capa;
    if (time < A[last - 1].first) time = A[last - 1].first;
    int distance = 0;
    int lastdist = 0;
    int totaldist = 0;
    set<pair<int, int> >::iterator it = dist.begin();
    for (; it != dist.end();) {
      int k = 0;
      set<pair<int, int> >::iterator jt = it;
      time += distance = it->first - lastdist;
      totaldist += distance;
      lastdist = it->first;
      for (; jt != dist.end() && jt->first == it->first; jt++) {
        times[jt->second] = time;
        k++;
        capa--;
      }
      time += 1 + k / 2;
      it = jt;
    }
    time += totaldist;
    distance = 0;
  }
  for (int i = 0; i < n; i++) cout << times[i] << " ";
  return 0;
}
