#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
char buf[1000];
string nextLine(int length = 100) {
  cin.getline(buf, length);
  string s(buf);
  return s;
}
string next(int length = 100) {
  string tmp;
  cin >> tmp;
  return tmp;
}
int nextInt() {
  int tmp;
  scanf("%d", &tmp);
  return tmp;
}
struct student {
  int time;
  int id;
  int stop;
  student(int t, int s, int x) {
    id = x;
    stop = s;
    time = t;
  }
  bool operator<(const student &o) const { return stop < o.stop; }
  student() {}
};
const int MAXN = 100100;
int ans[MAXN];
student ar[MAXN];
int main() {
  int n = nextInt(), m = nextInt();
  for (int i = 0, _i = (n); i < _i; ++i) {
    int a = nextInt(), b = nextInt();
    ar[i] = student(a, b, i);
  }
  int t = 0;
  for (int x = 0; x < n; x += m) {
    int top = min(n, x + m);
    t = max(t, ar[top - 1].time);
    sort(ar + x, ar + top);
    int wait = 0;
    int prstop = -1;
    int count = 0;
    for (int y = x; y < top; y++) {
      student s = ar[y];
      if (s.stop != prstop) {
        if (count) wait += 1 + count / 2;
        count = 0;
      }
      ans[s.id] = t + wait + s.stop;
      count++;
      prstop = s.stop;
    }
    wait += 1 + count / 2;
    t = t + wait + prstop;
    t += prstop;
  }
  string sep;
  for (int i = 0, _i = (n); i < _i; ++i) {
    cout << sep << ans[i];
    sep = " ";
  }
  cout << "\n";
}
