#include <bits/stdc++.h>
using namespace std;
int n, m;
int t[100100], x[100100], counter[100100];
int tt;
int arrived[100100];
int id[100100], ans[100100];
bool cmp(int u, int v) { return (x[u] < x[v]); }
void go(int first, int last) {
  int addition = 0;
  for (int i = first; i < last; i++) {
    id[i] = i;
    counter[x[i]]++;
    arrived[x[i]] = -1;
  }
  sort(id + first, id + last, cmp);
  for (int i = first; i < last; i++) {
    if (arrived[x[id[i]]] == -1) {
      arrived[x[id[i]]] = tt + addition + x[id[i]];
      addition += 1 + (counter[x[id[i]]] / 2);
    }
    ans[id[i]] = arrived[x[id[i]]];
  }
  tt += addition + *max_element(x + first, x + last) * 2;
  for (int i = first; i < last; i++) {
    printf("%d ", ans[i]);
    counter[x[i]]--;
    arrived[x[i]] = -1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d%d", &t[i], &x[i]);
  tt = 0;
  for (int first = 0; first < n;) {
    int last = min(first + m, n);
    tt = max(tt, t[last - 1]);
    go(first, last);
    first = last;
  }
}
