#include <bits/stdc++.h>
using std::ceil;
using std::cin;
using std::cout;
using std::endl;
using std::floor;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::queue;
using std::set;
using std::string;
using std::stringstream;
using std::swap;
using std::vector;
int main(void) {
  int n, m, empty_seats, students_left, bus_pos = 0, bus_pos_prev = 0;
  long long time = 0;
  pair<int, int> student;
  pair<int, int> student_in_bus;
  queue<pair<int, int> > station;
  queue<pair<int, int> > bus_exit;
  vector<int> result(100100);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> student.first >> student.second;
    station.push(student);
  }
  students_left = n;
  while (students_left > 0) {
    vector<pair<int, int> > bus;
    empty_seats = m;
    while (empty_seats > 0 && students_left > 0) {
      student_in_bus.first = station.front().second;
      student_in_bus.second = n - students_left + 1;
      bus.push_back(student_in_bus);
      if (time < station.front().first) time = station.front().first;
      station.pop();
      empty_seats--;
      students_left--;
    }
    sort(bus.begin(), bus.end());
    for (unsigned int i = 0; i < bus.size(); i++) {
      bus_exit.push(bus[i]);
    }
    while (bus_exit.size() > 0) {
      bus_pos_prev = bus_pos;
      bus_pos = bus_exit.front().first;
      time += bus_pos - bus_pos_prev;
      result[bus_exit.front().second] = time;
      bus_exit.pop();
      int k = 1;
      while (bus_exit.size() > 0 && bus_exit.front().first == bus_pos) {
        result[bus_exit.front().second] = time;
        k++;
        bus_exit.pop();
      }
      time += 1 + floor(k / 2);
    }
    time += bus_pos;
    bus_pos = 0;
  }
  for (int i = 1; i <= n; i++) {
    cout << result[i] << " ";
  }
  cout << endl;
  return 0;
}
