B. Даалгаваруудыг ажиллуулах

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ бодлогонд та нэг шугамт серверийн ажлын урсгалыг дуурайлгаж дүрслэх юм. Энд $n$ ширхэг ажиллуулах даалгаварууд байна, $i$-р нь $t_{i}$ мөчид ирэх ба $d_{i}$ нэгж хугацаанд ажиллах шаардлагатай. Бүх $t_{i}$ нь ялгаатай байна.

Даалгавар өгөгдөхөд сервер дараах гурван боломжит замаар хариу өгч болно:

  1. Сервер сул ба даалгаварын дараалал хоосон байвал сервер уг даалгаварыг шууд ажиллуулж эхэлнэ.
  2. Хэрвээ сервер завгүй ба дараалалд $b$-с бага тооны даалгавар байвал шинэ даалгавар дарааллын төгсгөлд нэмэгдэнэ.
  3. Хэрвээ сервер завгүй ба дараалалд аль хэдийн $b$ даалгавар хүлээгдэж байвал шинэ даалгавар зүгээр цуцлагдах ба хэзээ ч ажиллахгүй.

Сервер даалгаварыг аль болох хурдан ажиллуулж дуусгах ба дарааллаас дахин нэгийг авна (мэдээж дараалал хоосон биш байвал). Хэрвээ даалгавар $x$ мөчид ирсэн ба сервер өөр даалгаварыг яг ижил мөчид дуусгасан бол бид эхний даалгаварыг дарааллаас авсан ба зөвхөн шинэ даалгавар ирнэ гэж үзнэ.

Даалгавар бүрийн хувьд сервер уг даалгаварыг гүйцэтгэж дуусах мөчийг олох ба хэрвээ цуцлагдсан бол $-1$-г хэвлэ.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $b$ ($1 ≤ n, b ≤ 200 000$) байх ба даалгаваруудын тоо болон даалгаварын дарааллийн боломжит хамгийн их хэмжээ.

Дараагийн $n$ мөрөнд даалгаваруудын тайлбар байна (хугацааны эрэмбээр). Тайлбар бүр хоёр бүхэл тоон утга $t_{i}$ болон $d_{i}$ ($1 ≤ t_{i}, d_{i} ≤ 10^{9}$)-с тогтох ба энд $t_{i}$ нь $i$-р даалгаварын ирэх цаг ба $d_{i}$ нь үүнийг сервер ажиллуулах хугацаа. Бүх $i > 1$-н хувьд $t_{i - 1} < t_{i}$ байна.

Гаралт

$e_{i}$ нь сервер $i$-р даалгаварыг ажиллуулж дуусгах хугацаа байх эсвэл харгалзах даалгавар цуцлагдсан бол $ - 1$ байх $n$ ширхэг бүхэл тоонуудын дараалал $e_{1}, e_{2}, ..., e_{n}$-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 1
2 9
4 8
10 9
15 2
19 1
Гаралт
11 19 -1 21 22 
Оролт
4 1
2 8
4 8
10 9
15 2
Гаралт
10 18 27 -1 

Тэмдэглэл

Эхний жишээг авч үзье.

  1. $2$ мөчид сервер эхний даалгаварыг ажиллуулж эхлэх ба үүнийг $11$ мөчид ажиллуулж дуусгана.
  2. $4$ мөчид хоёр дахь даалгавар ирэх ба дараалалд нэмэгдэнэ.
  3. $10$ мөчид гурав дахь даалгавар ирнэ. Гэсэн хэдий ч сервер $1$-р даалгаварыг ажиллуулаад завгүй байгаа, $b = 1$ ба $2$-р даалгавар аль хэдийн дараалалд хүлээгдэж байгаа учраас гуравдугаар даалгавар цуцлагдана.
  4. $11$ мөчид сервер эхний даалгаварыг ажиллуулж дуусгах ба хоёрдугаар даалгаварыг дарааллаас авна.
  5. $15$ мөчид дөрөв дахь даалгавар ирнэ. Сервер завгүй байгаа учраас даалгавар дараалалд нэмэгдэнэ.
  6. $19$ мөчид хоёр үйл явдал зэрэг тохиолдоно: сервер хоёрдугаар даалгаварыг гүйцэтгэж дуусах ба тавдугаар даалгавар ирнэ. Дээр бодлогын нөхцөлд хэлсэнчлэн эхлээд сервер хоёрдугаар даалгаварыг дуусгах ба тэгээд дөрөвдүгээр даалгаварыг дарааллаас аваад тэгээд тавдугаар даалгавар ирнэ. Дараалал хоосон учраас тавдугаар даалгавар нэмэгдэнэ.
  7. Сервер $4$ дугаартай даалгаварыг $21$ мөчид ажиллуулж дуусгах ба $5$ дугаартай даалгаварыг дарааллаас авна.
  8. Сервер $5$ дугаартай даалгаварыг $22$ мөчид ажиллуулж дуусгана.
Сэтгэгдлүүдийг ачааллаж байна...