/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstring>


constexpr int32_t kMaxQueueSize = 100000;
constexpr int32_t kMaxProcessCount = kMaxQueueSize;
constexpr int32_t kMaxLengthProcessName = 10;
constexpr int32_t kMaxTime = 1000000;

void CallRoundRobin(std::istream &input_stream);

class Queue {
 public:
  Queue() noexcept;
  ~Queue() noexcept;
  void Push(const int32_t x);
  int32_t Pop();
  bool IsEmpty() const noexcept;
  bool IsFull() const noexcept;

 private:
  Queue(const Queue &obj) noexcept = delete;
  Queue &operator=(const Queue &obj) noexcept = delete;
  Queue(Queue &&obj) = delete;
  Queue &operator=(Queue &&obj) = delete;

  static int32_t GetNextPosition(const int32_t current_position) noexcept;

 private:
  int32_t depth_;
  int32_t tail_;
  int32_t indices_[kMaxQueueSize];  //!< DBへの参照インデックス
};

struct Process {
  char name[kMaxLengthProcessName + 1];
  int32_t remaining_time{0};
};

class ProcessGroup {
 public:
  ProcessGroup() noexcept;
  ~ProcessGroup() noexcept;
  int32_t AddAndGetStoredIndex(const std::string &name, const int32_t total_time);
  std::string GetProcessNameFromIndex(const int32_t index) const;
  int32_t ComputeAndReturnComputedTime(const int32_t index, const int32_t compute_time);
  bool AlreadyFinished(const int32_t index) const;

 private:
  ProcessGroup(const ProcessGroup &obj) noexcept = delete;
  ProcessGroup &operator=(const ProcessGroup &obj) noexcept = delete;
  ProcessGroup(ProcessGroup &&obj) = delete;
  ProcessGroup &operator=(ProcessGroup &&obj) = delete;

 private:
  int32_t number_of_process_;
  Process processes_[kMaxProcessCount];
};

class RoundRobin {
 public:
  explicit RoundRobin(const int32_t quantum_time) noexcept;
  ~RoundRobin() noexcept;
  void AddProcess(const std::string &name, const int32_t total_time);
  void ComputeOneQuantum();
  void Load(std::istream &input_stream);
  int32_t GetCurrentTime() const noexcept;
  bool AllProcessWasAlreadyFinished() const;

 private:
  RoundRobin() noexcept = delete;
  RoundRobin(const RoundRobin &obj) noexcept = delete;
  RoundRobin &operator=(const RoundRobin &obj) noexcept = delete;
  RoundRobin(RoundRobin &&obj) = delete;
  RoundRobin &operator=(RoundRobin &&obj) = delete;

 private:
  const int32_t quantum_;
  int32_t current_time_;
  Queue process_queue_;
  ProcessGroup processes_;
};

void CallRoundRobin(std::istream &input_stream) {
  int32_t number_of_processes;
  int32_t qms;
  input_stream >> number_of_processes >> qms;
  RoundRobin *round_robin = new RoundRobin(qms);
  try {
    for (int32_t process_index = 0; process_index < number_of_processes; ++process_index) {
      std::string process_name;
      int32_t total_processing_time;
      input_stream >> process_name >> total_processing_time;
      round_robin->AddProcess(process_name, total_processing_time);
    }

    while (round_robin->GetCurrentTime() < kMaxTime) {
      round_robin->ComputeOneQuantum();
      if (round_robin->AllProcessWasAlreadyFinished()) {
        break;
      }
    }
  } catch (...) {
    delete round_robin;
    std::cout << "ERROR" << std::endl;
  }
  delete round_robin;
}

Queue::Queue() noexcept : depth_(0), tail_(0), indices_{0} {}

Queue::~Queue() noexcept {}

bool Queue::IsEmpty() const noexcept {
  return (depth_ <= 0);
}

bool Queue::IsFull() const noexcept {
  return (depth_ >= kMaxQueueSize);
}

void Queue::Push(const int32_t x) {
  if (IsFull()) {
    std::cout << "ERROR: Push(): queue is full." << std::endl;
    throw 1;
  }
  const int32_t top_position = (tail_ + depth_) % kMaxQueueSize;
  indices_[top_position] = x;
  ++depth_;
}

int32_t Queue::Pop() {
  if (IsEmpty()) {
    std::cout << "ERROR: Pop(): queue is empty." << std::endl;
    throw 1;
  }
  int32_t value = indices_[tail_];
  tail_ = GetNextPosition(tail_);
  --depth_;
  return value;
}

int32_t Queue::GetNextPosition(const int32_t current_position) noexcept {
  return ((current_position + 1) % kMaxQueueSize);
}

// ******************************
ProcessGroup::ProcessGroup() noexcept : number_of_process_(0), processes_{} {}
ProcessGroup::~ProcessGroup() noexcept {}

int32_t ProcessGroup::AddAndGetStoredIndex(const std::string &name, const int32_t total_time) {
  if (number_of_process_ >= kMaxProcessCount) {
    std::cout << "ERROR: ProcessGroup::AddProcess(): too many processes." << std::endl;
    throw 1;
  }
  const int32_t index_to_store = number_of_process_;
  ++number_of_process_;
  strncpy(processes_[index_to_store].name, name.c_str(), kMaxLengthProcessName);
  processes_[index_to_store].remaining_time = total_time;
  return index_to_store;
}

std::string ProcessGroup::GetProcessNameFromIndex(const int32_t index) const {
  if ((index < 0) && (index >= number_of_process_)) {
    std::cout << "ERROR: ProcessGroup::GetProcessNameFromIndex(): invalid index." << std::endl;
  }
  return std::string(processes_[index].name);
}

int32_t ProcessGroup::ComputeAndReturnComputedTime(const int32_t index, const int32_t compute_time) {
  int32_t computed_time = 0;
  if ((index < 0) && (index >= number_of_process_)) {
    std::cout << "ERROR: ProcessGroup::ComputeOneQuantum(): invalid index." << std::endl;
    throw 1;
  } else if (processes_[index].remaining_time == 0) {
    std::cout << "ERROR: ProcessGroup::ComputeOneQuantum(): already finished." << std::endl;
    throw 1;
  } else {
    const int32_t previous_remaining_time = processes_[index].remaining_time;
    processes_[index].remaining_time = std::max(0, previous_remaining_time - compute_time);
    computed_time = previous_remaining_time - processes_[index].remaining_time;
  }
  return computed_time;
}

bool ProcessGroup::AlreadyFinished(const int32_t index) const {
  if ((index < 0) && (index >= number_of_process_)) {
    std::cout << "ERROR: ProcessGroup::AlreadyFinished(): invalid index." << std::endl;
  }
  return (processes_[index].remaining_time == 0);
}

// ******************************
RoundRobin::RoundRobin(const int32_t quantum_time) noexcept
    : quantum_(quantum_time), current_time_(0), process_queue_{}, processes_{} {}
RoundRobin::~RoundRobin() noexcept {}

void RoundRobin::AddProcess(const std::string &name, const int32_t total_time) {
  try {
    const int32_t stored_index = processes_.AddAndGetStoredIndex(name, total_time);
    process_queue_.Push(stored_index);
  } catch (...) {
    throw;
  }
}

void RoundRobin::ComputeOneQuantum() {
  try {
    const int32_t process_index = process_queue_.Pop();
    const int32_t computed_time = processes_.ComputeAndReturnComputedTime(process_index, quantum_);
    current_time_ += computed_time;
    if (processes_.AlreadyFinished(process_index)) {
      std::cout << processes_.GetProcessNameFromIndex(process_index) << " " << current_time_ << std::endl;
    } else {
      process_queue_.Push(process_index);
    }
  } catch (...) {
    throw;
  }
}

int32_t RoundRobin::GetCurrentTime() const noexcept {
  return current_time_;
}

bool RoundRobin::AllProcessWasAlreadyFinished() const {
  return process_queue_.IsEmpty();
}

int main(int argc, char *argv[]) {
  CallRoundRobin(std::cin);
  return 0;
}



Measured memory_bytes: 4648