#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
template <typename T>
T pow(T a, T b, long long m) {
  T ans = 1;
  while (b > 0) {
    if (b % 2 == 1) ans = (ans * a) % m;
    b /= 2;
    a = (a * a) % m;
  }
  return ans % m;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, m;
  cin >> n >> m;
  long long ans[n];
  long long t[n], x[n];
  vector<pair<long long, long long> > v;
  for (int i = 0; i < n; i++) {
    cin >> t[i] >> x[i];
  }
  int i = 0;
  int time = 0;
  int time1 = 0;
  map<long long, long long> m1;
  set<long long> s;
  while (i < n) {
    m1.clear();
    v.clear();
    s.clear();
    long long t1 = 0;
    for (int j = i; j < m + i && j < n; j++) {
      t1 = max(t1, t[j]);
    }
    for (int j = i; j < m + i && j < n; j++) {
      if (t1 > time)
        v.push_back(make_pair(t1 + x[j], j));
      else
        v.push_back(make_pair(time + x[j], j));
    }
    sort(v.begin(), v.end());
    for (int j = 0; j < v.size(); j++) {
      m1[v[j].first]++;
    }
    int k = 0;
    int cnt = 0;
    while (k < v.size()) {
      if (s.find(v[k].first) == s.end()) {
        cnt = m1[v[k].first];
        while (cnt) {
          ans[v[k].second] = v[k].first + time1;
          cnt--;
          k++;
        }
        cnt = 0;
        k--;
        if (k >= 0 && k < v.size()) {
          s.insert(v[k].first);
          time1 += 1 + (m1[v[k].first] / 2);
        }
        k++;
      }
    }
    time = ans[v[v.size() - 1].second] + 1 + (m1[v[v.size() - 1].first] / 2) +
           x[v[v.size() - 1].second];
    i += m;
    time1 = 0;
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
}
