#include <bits/stdc++.h>
using namespace std;
struct comp {
  bool operator()(const vector<int>& lhs, const vector<int>& rhs) const {
    return lhs.size() > rhs.size();
  }
};
struct comps {
  bool operator()(const string& lhs, const string& rhs) const {
    return lhs > rhs;
  }
};
bool ff(pair<int, int> a, pair<int, int> b) { return a.first < b.first; }
double dis(double x1, double y1, double x2, double y2) {
  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
int gcd(long long unsigned int a, long long unsigned int b) {
  return (b == 0) ? a : gcd(b, a % b);
}
int comb(int a, int b) {
  if (a == 0) return 1;
  if (a < b) return 1;
  if (a == b) return 1;
  if (b == 1) return a;
  if (b == 0) return 1;
  long long unsigned int aa = 1, bb = 1;
  for (int i = b; i > 0; i--, a--) {
    aa *= a;
    bb *= i;
    int gc = gcd(aa, bb);
    if (gc > 1) {
      aa /= gc;
      bb /= gc;
    }
  }
  return aa % 1000000007;
}
bool isprime(long long unsigned int n) {
  for (int i = 2; i <= sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}
bool f(pair<int, int> p1, pair<int, int> p2) {
  if (p1.first < p2.first)
    return true;
  else if ((p1.first == p2.first) && (p1.second > p2.second))
    return true;
  else
    return false;
}
int t[100005];
int x[100005];
int v[100005];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) cin >> t[i] >> x[i];
  int i = 0;
  int nn = n;
  int kalkis = 0;
  int delay = 0;
  while (n > 0) {
    int p = (n >= m) ? m : n;
    n -= p;
    kalkis =
        (t[i + p - 1] > (kalkis + delay)) ? t[i + p - 1] : (kalkis + delay);
    map<int, int> mapp;
    map<int, vector<int> > duranlar;
    for (int j = i; j < i + p; j++) {
      mapp[x[j]]++;
      duranlar[x[j]].push_back(j);
    }
    map<int, int>::iterator it;
    delay = 0;
    for (it = mapp.begin(); it != mapp.end(); it++) {
      for (int k = 0; k < duranlar[it->first].size(); k++) {
        v[duranlar[it->first][k]] = kalkis + delay + (it->first);
      }
      delay += 1 + (it->second) / 2;
    }
    it--;
    delay += 2 * (it->first);
    i += p;
  }
  for (int i = 0; i < nn; i++) cout << v[i] << " ";
  return 0;
}
