#include <bits/stdc++.h>
using namespace std;
struct stud {
  int id;
  int t;
  int x;
};
bool comp(stud a, stud b) { return a.x < b.x; }
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> ans(n, 0);
  int wt = 0;
  int buses = 0;
  while (n) {
    int i = 0;
    vector<stud> s;
    while (n && i < m) {
      n--;
      stud T;
      cin >> T.t >> T.x;
      T.id = i + buses * m;
      s.push_back(T);
      i++;
    }
    buses++;
    wt = max(wt, s.back().t);
    sort(s.begin(), s.end(), comp);
    int t = 0;
    int k = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (i && s[i].x != s[i - 1].x) {
        t = t + 1 + k / 2;
        k = 1;
      } else
        k++;
      ans[s[i].id] = wt + t + s[i].x;
    }
    wt += 2 * s.back().x + t + 1 + k / 2;
  }
  for (int i = 0; i < ans.size() - 1; ++i) {
    cout << ans[i] << ' ';
  }
  cout << ans.back() << endl;
}
