#include <bits/stdc++.h>
using namespace std;
const int INFint = 2e9;
const long long INF = 1e18;
const long long MOD = 1000000007ll;
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int> > block;
  vector<int> ans(n);
  int time = 0;
  for (int i = 0; i < n; i++) {
    int t, x;
    cin >> t >> x;
    block.push_back({x, i});
    if (block.size() == m || i == n - 1) {
      time = max(t, time);
      int it = 0;
      sort(block.begin(), block.end());
      int pv = 0;
      while (it < block.size()) {
        time += block[it].first - pv;
        pv = block[it].first;
        ans[block[it].second] = time;
        int cnt = 1;
        it++;
        while (it < block.size() && block[it - 1].first == block[it].first) {
          ans[block[it].second] = time;
          cnt++;
          it++;
        }
        time += 1 + cnt / 2;
      }
      time += block.back().first;
      block.clear();
    }
  }
  for (auto x : ans) cout << x << ' ';
  fprintf(stderr, "\nTIME = %lf\n", 1.0 * clock() / CLOCKS_PER_SEC);
  ;
  return 0;
}
