#include <bits/stdc++.h>
using namespace std;
int main() {
  if (0) freopen("in.txt", "r", stdin);
  int n, m;
  int second, j, k, np, b;
  long long t, t2, bt;
  static int sx[100005];
  static long long st[100005], out[100005];
  static pair<int, int> bus[100005];
  queue<int> W;
  scanf("%d%d", &n, &m);
  for (second = 0; second < n; second++) cin >> st[second] >> sx[second];
  for (t = bt = 1, second = b = 0;;) {
    while ((second < n) && (st[second] <= t)) W.push(second++);
    while ((t >= bt) && (b < m) && (!W.empty())) {
      j = W.front(), W.pop();
      bus[b++] = make_pair(sx[j], j);
    }
    if ((b == m) || (second == n) && (W.empty())) {
      sort(bus, bus + b);
      for (j = 0, t2 = t; j < b;) {
        if (!j)
          t2 += bus[j].first;
        else
          t2 += bus[j].first - bus[j - 1].first;
        for (k = j + 1; (k < b) && (bus[j].first == bus[k].first); k++)
          ;
        np = k - j;
        for (; j < k; j++) out[bus[j].second] = t2;
        t2 += 1 + np / 2;
      }
      t2 += bus[b - 1].first;
      bt = t2;
      b = 0;
      if ((second == n) && (W.empty())) break;
      t = t2;
    } else
      t++;
  }
  for (second = 0; second < n; second++)
    cout << out[second] << (second < n - 1 ? ' ' : '\n');
  return (0);
}
