#include <bits/stdc++.h>
using namespace std;
int w[100000];
int d[100000];
int q[10010];
int main() {
  int m, n, x, t;
  cin >> n >> m;
  int cnt = 0, time = 0, temp = 0;
  for (int i = 0; i < n;) {
    int j = 0;
    while (i < n && j < m) {
      cin >> t >> x;
      w[i] = x;
      d[j] = w[i];
      j++;
      i++;
    }
    if (t > time) {
      temp = t;
      cnt += t - cnt;
    } else
      temp = time;
    sort(d, d + j);
    q[d[0]] = 0;
    cnt += d[j - 1] * 2;
    int emp = 1, acc = 0;
    for (int s = 0; s < j;) {
      emp = 1;
      s++;
      while (s < j && d[s] == d[s - 1]) {
        emp++;
        s++;
      }
      if (s < j) {
        q[d[s]] = acc += emp / 2 + 1;
        cnt += emp / 2 + 1;
      }
    }
    cnt += emp / 2 + 1;
    for (int s = i - j; s < i; s++) {
      w[s] += q[w[s]];
      w[s] += temp;
    }
    time = cnt;
  }
  for (int i = 0; i < n; i++) cout << w[i] << " ";
  return 0;
}
