K. Ажил гүйцэтгэх

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

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

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

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

Вася дурын ажлуудыг гүйцэтгэх тооцоолох систем бүтээхийг хүсч байна. Түүнд програмын нэг хэсэг болох ажлуудыг гүйцэтгэх дарааллыг сонгодог алгоритм хэрэгтэй.

Тэр дараах алгоритмтай болсон:

  • Гүйцэтгэх ажлуудын нэг дараалал байна. Ажил гүйцэтгэгдэхийн тулд дараалалд нэмэгдсэн байх хэрэгтэй.
  • Ажил бүрийн хувьд хоёр утга мэдэгдэж байна: $l_{i}$ ба $t_{i}$. Эдгээр нь ажлыг гүйцэтгэж дуусахад шаардлагатай секундын тоо болон энэ ажил гүйцэтгэх дараалалд нэмэгдсэн хугацааны агшин байна.
  • Хэрвээ хугацааны $T$ агшинд алгоритм ажиллуулах ажлаа сонговол хамгийн бага $l_{i} - (T - t_{i})^{2}$ утгатайг нь сонгоно. Хэрвээ энэ утга нь тэнцүү ажлууд байвал хамгийн бага индекстэйг нь сонгоно. Тэгээд дараагийн $l_{i}$ секундэд алгоритм ажил дуусахыг хүлээнэ.

Алгоритмыг шалгахын тулд Вася таныг үүнийг дууриалган ажиллуулахыг хүсч байна.

Танд $n$ ажил өгөгдсөн. Ажил бүрийн хувьд та ажиллаж дуусахад шаардлагатай секундын тоо $l_{i}$ болон энэ ажил гүйцэтгэх дараалалд нэмэгдсэн хугацааны агшинг илэрхийлэх $t_{i}$ утгыг мэдэж байна.

Ажил бүрийн хувьд уг ажил хийгдэж дуусах хугацааны агшинг ол.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 10^{5})$ байх ба ажиллуулах ажлуудын тоо. Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга: $l_{i},  t_{i}$ $(1 ≤ l_{i} ≤ 10^{5},  0 ≤ t_{i} ≤ 10^{5})$ байна.

Гаралт

Зайгаар тусгаарлагдсан $n$ бүхэл тоон утгыг хэвлэ. $i$-р бүхэл тоон утга нь $i$-р ажлын ажиллаж дуусах хугацааны агшин байна.

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

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

Оролт
1
10 5
Гаралт
15 
Оролт
3
3 0
4 3
5 2
Гаралт
3 7 12 
Оролт
3
3 0
4 2
5 1
Гаралт
3 12 8 
Оролт
6
3 0
5 1
4 2
5 18
4 19
5 14
Гаралт
3 8 12 24 28 19 
Сэтгэгдлүүдийг ачааллаж байна...