#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:4000000")
struct Student {
  int t, first;
  int num;
  inline bool operator<(const Student& other) const {
    return first < other.first;
  }
};
int n, m;
int last;
Student a[100000];
int out[100000];
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = (0); (i) < (n); ++(i)) {
    scanf("%d%d", &a[i].t, &a[i].first);
    a[i].num = i;
  }
  int i = 0;
  while (i < n) {
    int k = min(i + m, n);
    int ans = max(a[k - 1].t, last), wait = 0;
    int maxTime = 0, maxDist = 0;
    map<int, int> cnt;
    vector<Student> b;
    for (int(j) = (i); (j) < (k); ++(j)) {
      b.push_back(a[j]);
      cnt[a[j].first]++;
    }
    sort(b.begin(), b.end());
    for (int(j) = (0); (j) < (b.size()); ++(j)) {
      int tmp = ans + b[j].first + wait;
      out[b[j].num] = tmp;
      if (j + 1 == b.size() || b[j].first != b[j + 1].first)
        wait += cnt[b[j].first] / 2 + 1;
      tmp = ans + b[j].first + wait;
      if (tmp > maxTime) {
        maxTime = tmp;
        if (b[j].first > maxDist) maxDist = b[j].first;
      }
    }
    last = maxTime + maxDist;
    i = k;
  }
  for (int(i) = (0); (i) < (n); ++(i)) printf("%d ", out[i]);
}
