#include <bits/stdc++.h>
using namespace std;
struct student {
  int i;
  int t, x;
};
bool myless(student &st1, student &st2) {
  if (st1.x < st2.x) return true;
  return false;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> res(n);
  vector<student> v(n);
  for (int i = 0; i < n; i++) {
    student st;
    st.i = i;
    cin >> st.t >> st.x;
    v[i] = st;
  }
  int t = 0;
  int n_size = n;
  int ind = 0;
  while (n_size > 0) {
    int x = 0;
    int imaxt = 0;
    vector<student> car;
    if (n_size - m >= 0) {
      car.resize(m);
      for (int i = ind; i < ind + m; i++) {
        imaxt = max(imaxt, v[i].t);
        car[i - ind] = v[i];
      }
      ind += m;
    } else {
      car.resize(n_size);
      for (int i = ind; i < ind + n_size; i++) {
        imaxt = max(imaxt, v[i].t);
        car[i - ind] = v[i];
      }
      ind += n_size;
    }
    sort(car.begin(), car.end(), myless);
    n_size -= m;
    t = max(t, imaxt);
    int carsize = car.size();
    for (int i = 0; i < carsize; i++) {
      int cnt = 1;
      int ibeg = i;
      while ((i + 1) < carsize && car[i].x == car[i + 1].x) {
        cnt++;
        i++;
      }
      t += (car[i].x - x);
      x = car[i].x;
      for (int j = ibeg; j < ibeg + cnt; j++) res[car[j].i] = t;
      t += 1 + cnt / 2;
    }
    t += car[carsize - 1].x;
  }
  for (int i = 0; i < n; i++) cout << res[i] << ' ';
  return 0;
}
