#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
int main() {
  int n, m, t, x, time = 0, i;
  vector<pair<int, int> > v;
  vector<int> ans;
  cin >> n >> m;
  for (int i = 0; i < (n); i++) {
    cin >> t >> x;
    v.push_back(make_pair(t, x));
  }
  for (i = 0; i < n; i += m) {
    x = min(n, i + m);
    time = max(time, (v[x - 1].first));
    map<int, int> mp;
    for (int j = i; j < x; j++) mp[v[j].second]++;
    int arr[10003] = {0}, last = 0;
    for (typeof(mp.begin()) it = mp.begin(); it != mp.end(); it++) {
      time += (it->first) - last;
      arr[it->first] = time;
      time = time + 1 + (int)(it->second) / 2;
      last = it->first;
    }
    time += last;
    for (int j = i; j < x; j++) {
      ans.push_back(arr[v[j].second]);
    }
    mp.clear();
  }
  for (typeof(ans.begin()) it = ans.begin(); it != ans.end(); it++)
    cout << *it << " ";
  cout << endl;
  return 0;
}
