#include <bits/stdc++.h>
using namespace std;
struct student {
  int t, x, res;
};
bool by_t(student x, student y) { return (x.t < y.t); }
bool by_x(student x, student y) { return (x.x < y.x); }
int n, m, cur_t, z;
student temp;
vector<student> a, b;
int main() {
  cin >> n >> m;
  for (int x = 0; x < n; x++) {
    cin >> temp.t >> temp.x;
    a.push_back(temp);
    if (a.size() == m || x == n - 1) {
      cur_t = max(cur_t, a[a.size() - 1].t);
      sort(a.begin(), a.end(), by_x);
      z = 0;
      for (int j = 0; j < a.size(); j++) {
        if (j && a[j - 1].x != a[j].x) {
          cur_t += z / 2 + 1;
          z = 0;
        }
        a[j].res = cur_t + a[j].x;
        z++;
        b.push_back(a[j]);
      }
      cur_t += z / 2 + 1;
      cur_t += 2 * a[a.size() - 1].x;
      a.clear();
    }
  }
  sort(b.begin(), b.end(), by_t);
  for (int i = 0; i < n; i++) cout << b[i].res << ' ';
}
