#include <bits/stdc++.h>
using namespace std;
int main() {
  long n, m, t, d;
  long long T = 0;
  cin >> n >> m;
  priority_queue<long> PeopleForDest[10002];
  while (n) {
    if (n >= m)
      n = n - m;
    else {
      m = n;
      n = 0;
    }
    map<long, long> Dest;
    map<long, long>::iterator it;
    long long* getDownAt = new long long[m];
    for (long i = 0; i < m; i++) {
      cin >> t >> d;
      Dest[d]++;
      PeopleForDest[d].push(i);
      if (T < t) T = t;
    }
    long lastd = 0;
    for (it = Dest.begin(); it != Dest.end(); it++) {
      d = it->first;
      int GetDownTime = 1 + PeopleForDest[d].size() / 2;
      T = T + d - lastd;
      lastd = d;
      while (!PeopleForDest[d].empty()) {
        getDownAt[PeopleForDest[d].top()] = T;
        PeopleForDest[d].pop();
      }
      T = T + GetDownTime;
    }
    for (long i = 0; i < m; i++) cout << getDownAt[i] << " ";
    T = T + d;
  }
  cout << endl;
  return 0;
}
