#include <bits/stdc++.h>
using namespace std;
int res[100010];
int num[100010];
int main() {
  map<int, int> s;
  int n, m, k, t = 0, tt;
  cin >> n >> m;
  for (int i = 0; i < n;) {
    s.clear();
    for (int j = 0; j < m && i < n; i++, j++) {
      cin >> tt >> k;
      t = max(tt, t);
      s[k]++;
      num[j] = k;
      num[j + 1] = 0;
    }
    int last = 0;
    for (map<int, int>::iterator it = s.begin(); it != s.end(); it++) {
      t += it->first - last;
      res[it->first] = t;
      t += 1 + it->second / 2;
      last = it->first;
    }
    t += s.rbegin()->first;
    k = 0;
    while (num[k]) {
      cout << res[num[k]] << " ";
      k++;
    }
  }
  cout << endl;
  return 0;
}
