C. Автобус

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

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

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

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

Их сургуулийн ойролцоо автобусны буудал байдаг. Хичээл дууссаны дараа $n$ тооны оюутан буудал дээр ирдэг. $i$-р оюутан $t_{i}$ (бүх $t_{i}$ тоонууд ялгаатай) хугацааны агшинд автобусны буудал дээр ирнэ.

Бид автобусны буудлыг $Ox$ тэнхлэгийн $x=0$ цэг дээр байх ба автобус $Ox$ тэнхлэгийн дагуу явдаг гэж үзнэ. Өөрөөр хэлбэл, автобус координатын тэнхлэгийн нэмэх чиглэлийн дагуу явж, буцаж ирдэг гэж үзнэ. $i$-р оюутан $x_{i}$ ($x_{i}>0$) координаттай цэгт очих хэрэгтэй.

Автобус дараах алгоритмын дагуу хөдөлнө. Эхлээд автобус $0$ цэг дээр байна. Оюутнууд буудал дээр тогтмол ирэх ба тэд бүгд автобусанд сууна. Автобус $m$ тооны зорчигчдыг суулгах багтаамжтай. $m$ тооны оюутан автобусанд суухад автобус нэмэх чиглэлийн дагуу хөдөлж эхэлнэ. Мөн сүүлийн ($n$-р) оюутныг суухад автобус хөдөлнө. Автобус $1$ нэгж хугацаанд $1$ нэгж зай явдаг. Жишээлбэл, $y$ хугацаанд $y$ замыг туулна.

Дор хаяж $1$ оюутны автобуснаас буух цэг өнгөрөхөд автобус зогсож, оюутанг буулгана. Оюутнууд автобуснаас буухад $1+[k/2]$ нэгж хугацаа шаардагдана. Энд, $k$ нь энэ цэг дээр буух оюутны тоо байна. $[k/2]$ илэрхийлэл нь $k/2$ тооны бүхэл хэсгийг илтгэнэ. Сүүлийн оюутан автобуснаас буухад автобус буцаад $x=0$ цэг рүү явна. $x=0$ цэг рүү очих хүртэл автобус нэг ч зогсохгүй. Уг цэг дээр очоод автобус оюутнуудаар өөрийгөө дүүргээд, өмнөх үйлдлүүдийг давтана.

Оюутнууд автобус байхгүй үед буудалд ирвэл тэд шулуун (дараалал) үүсгэж, ирсэн дарааллаараа автобусанд сууна. Автобусанд хэдэн ч оюутан суусан маш бага хугацаа зарцуулах ба үүнд хугацаа орохгүй гэж тооцно уу. Мөн бусад ямар ч үйлдэлд хугацаа орохгүй. Автобусанд оюутнуудаас өөр зорчигчид байхгүй.

Оюутан бүр автобуснаас буух хугацааг тодорхойлох програм бичээрэй. Оюутны автобуснаас буух хугацаа гэдэг нь автобус оюутны хүрэх газарт зогссон хугацаа юм (бүлэг оюутан автобуснаас буухад хугацаа зарцуулдаг гэдгийг эс тооцвол).

Оролт

Эхний мөр нь оюутнуудын тоо болон автобусны зөөвөрлөж чадах зорчигчдын тоог харуулах, зайгаар тусгаарлагдсан, $n, m$ ($1≤n, m≤10^{5}$) хоёр бүхэл тоог агуулна. Дараагийн $n$ мөрүүд тус бүрдээ оюутнуудын тодорхойлолтыг агуулна. Мөр бүр нь $t_{i}, x_{i}$ ($1≤t_{i}≤10^{5}, 1≤x_{i}≤10^{4}$) гэсэн 2 бүхэл тоог агуулна. Мөрүүдэд $t_{i}$ тоог өсөх байдлаар дараалуулан өгнө. $x_{i}$ тоонуудын утга давхцаж болно.

Гаралт

Оюутнуудын автобуснаас буух үеийн хугацааг харуулах $n$ ширхэг $w_{1}, w_{2}, ..., w_{n}$ тоонуудыг нэг мөрөнд, хоосон зайгаар тусгаарлан хэвлэнэ үү.

Орчуулсан: Солонго

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

Оролт
1 10
3 5
Гаралт
8
Оролт
2 1
3 5
4 5
Гаралт
8 19
Оролт
5 4
3 5
4 5
5 5
6 5
7 1
Гаралт
11 11 11 11 20
Оролт
20 4
28 13
31 13
35 6
36 4
52 6
53 4
83 2
84 4
87 1
93 6
108 4
113 6
116 1
125 2
130 2
136 13
162 2
166 4
184 1
192 2
Гаралт
51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195

Тэмдэглэл

Эхний жишээнд, автобус эхний оюутныг $3$ нэгж хугацаанд хүлээж, $5$ нэгж хугацаанд хүрэх газар нь хүргэж өгч байна. Тиймээс оюутан автобуснаас $3+5=8$ хугацааны агшинд бууна.

2 дахь жишээнд, автобусны багтаамж $1$ учраас эхний оюутныг ганцааранг нь хүргэж өгнө. Энэ оюутан эхний жишээн дэх оюутантай ижил учир автобус $8$ хугацаанд хүрэх газраа хүрч, оюутныг буулгахад $1+[1/2]=1$ нэгж хугацаа зарцуулаад, буцаад $0$ цэгт хүртлээ нэмж $5$ нэгж хугацаа зарцуулна. Тиймээс автобус $14$ хугацааны агшинд буудал дээр буцаж ирнэ. Энэ үед $2$ дахь оюутан буудал дээр аль хэдийн ирчихсэн байна. Тиймээс тэр даруй автобусанд суун, хүрэх газраа хүртэл $5$ нэгж хугацаанд явна. Тэндээ $14+5=19$ хугацааны агшинд хүрнэ.

3 дахь жишээнд, автобус $4$ дахь оюутныг $6$ нэгж хугацаа хүртэл хүлээгээд эхний дөрвөн оюутныг авч явна, $5$ нэгж хугацаанд явж, $1+[4/2]=3$ нэгж хугацааг зорчигчдоо буулгахад зарцуулаад, $5$ нэгж хугацаанд буцаж очих ба дараа нь $5$ дахь оюутныг $1$ нэгж хугацаанд хүргэж өгч байна.

Сэтгэгдлүүдийг ачааллаж байна...