#include <bits/stdc++.h>
using namespace std;
int stu[100002][2], arr[100002], sta[10002];
map<int, int> des;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  int tm = 0;
  int cnt = 0, mxdis = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &stu[i][0], &stu[i][1]);
    mxdis = max(mxdis, stu[i][1]);
    des[stu[i][1]]++;
    cnt++;
    if (cnt == m || i == n - 1) {
      int pre = 0;
      tm = max(tm, stu[i][0]);
      for (map<int, int>::iterator it = des.begin(); it != des.end(); it++) {
        tm += (it->first - pre);
        sta[it->first] = tm;
        tm += (1 + (it->second / 2));
        pre = it->first;
      }
      for (int j = cnt - 1; j >= 0; j--) {
        arr[i - j] = sta[stu[i - j][1]];
      }
      tm += mxdis;
      des.clear();
      mxdis = 0;
      cnt = 0;
    }
  }
  printf("%d", arr[0]);
  for (int i = 1; i < n; i++) {
    printf(" %d", arr[i]);
  }
  printf("\n");
  return 0;
}
