#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const double PI = acos(-1);
const double EPS = 1e-8;
int t[100000];
int x[100000];
int ans[100000];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (int)n; ++i) cin >> t[i] >> x[i];
  int now = 0;
  int tm = 0;
  while (now < n) {
    map<int, vector<int> > xmap;
    int i;
    for (i = now; i < min(now + m, n); ++i) {
      xmap[x[i]].push_back(i);
      tm = max(tm, t[i]);
    }
    now = i;
    int pre = 0;
    int xmax = 0;
    for (__typeof((xmap).begin()) it = (xmap).begin(); it != (xmap).end();
         ++it) {
      xmax = max(it->first, xmax);
      tm += it->first - pre;
      pre = it->first;
      for (__typeof((it->second).begin()) jt = (it->second).begin();
           jt != (it->second).end(); ++jt) {
        ans[*jt] = tm;
      }
      tm += 1 + it->second.size() / 2;
    }
    tm += xmax;
  }
  for (int i = 0; i < (int)n; ++i) {
    if (i) cout << " ";
    cout << ans[i];
  }
}
