#include <bits/stdc++.h>
using namespace std;
map<int, vector<int> > a;
int ans[100100];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int t = 0;
  int k = 0;
  for (int i = 0; i < n; i++) {
    k++;
    int x, y;
    scanf("%d%d", &x, &y);
    a[y].push_back(i);
    if (k == m || i == n - 1) {
      t = max(t, x);
      map<int, vector<int> >::iterator j;
      j = a.begin();
      int X = 0;
      while (j != a.end()) {
        t += j->first - X;
        for (int L = 0; L < j->second.size(); L++) ans[j->second[L]] = t;
        t += (1 + j->second.size() / 2);
        X = j->first;
        j++;
        if (j == a.end()) t += X;
      }
      a.clear();
      k = 0;
    }
  }
  for (int i = 0; i < n; i++) printf("%d ", ans[i]);
  return 0;
}
