#include <bits/stdc++.h>
using namespace std;
int t[100005];
int x[100005];
map<int, int> M;
map<int, int> ans;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", t + i, x + i);
  }
  int mx = 0, st = 0, last = 0;
  for (int i = 1; i <= n; ++i) {
    st = max(st, t[i - 1]);
    M[x[i - 1]]++;
    if (i == n || i % m == 0) {
      for (map<int, int>::iterator it = M.begin(); it != M.end(); ++it) {
        ans[it->first] = st + it->first;
        st += 1 + it->second / 2;
      }
      for (int j = last; j < i; ++j) {
        printf("%d ", ans[x[j]]);
      }
      st += 2 * M.rbegin()->first;
      M.clear();
      ans.clear();
      last = i;
    }
  }
  return 0;
}
