#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
long long ncr[305][305] = {0};
void gen_ncr(int n) {
  int i, j;
  for ((i) = 0; (i) < (n + 1); i++) ncr[i][0] = 1;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) ncr[i][j] = ncr[i - 1][j] + ncr[i - 1][j - 1];
}
template <class T>
vector<T> TIV(int n) {
  vector<T> V;
  T a;
  int i;
  for ((i) = 0; (i) < (n); i++) {
    cin >> a;
    V.push_back(a);
  }
  return V;
}
double dis(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
struct node {
  int id;
  int t, x;
};
bool cmp(const node &a, const node &b) {
  if (a.x != b.x) return a.x < b.x;
  return a.id < b.id;
}
int main() {
  int test, cases = 1;
  int n, m;
  cin >> n >> m;
  vector<node> students;
  vector<node> bus;
  int i;
  for (i = 0; i < n; i++) {
    node a;
    a.id = i;
    cin >> a.t >> a.x;
    students.push_back(a);
  }
  reverse(students.begin(), students.end());
  int tm = 0;
  int res[101000];
  while (students.size()) {
    while (bus.size() < m && students.size()) {
      bus.push_back(students.back());
      if (tm < students.back().t) tm = students.back().t;
      students.pop_back();
    }
    sort(bus.begin(), bus.end(), cmp);
    reverse(bus.begin(), bus.end());
    int overhead = 0;
    int lastx;
    while (bus.size()) {
      node a = bus.back();
      lastx = a.x;
      int cnt = 0;
      while (bus.size() && bus.back().x == a.x) {
        res[bus.back().id] = tm + a.x + overhead;
        bus.pop_back();
        cnt++;
      }
      overhead += 1 + cnt / 2;
    }
    tm += lastx + overhead + lastx;
  }
  for (i = 0; i < n; i++) {
    if (i) cout << " ";
    cout << res[i];
  }
  cout << endl;
  return 0;
}
