Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
D. Видео нягтруулах статистик
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нохойнд зориулсан нийгмийн сүлжээ DH (Нохойн Байшин) нь муурнуудын бичлэгийг нягтруулан сүлжээнд байршуулахын тулд $k$ ширхэг онцгой сервертэй болсон. Бичлэг болгоныг сүлжээнд байршсаны дараа аль нэг сервер дээр нягтруулан шахдаг. Ингэж шахсанаар нийгмийн сүлжээнд хадгалж болдог.
Сервэр болгон нэг минутын урттай бичлэгийг нэг секундын хугацаанд нягтруулан шахдаг. Тиймээс аль ч сервер $m$ минутын бичлэгийг шахахын тулд $m$ секунд шаарддаг гэсэн үг.
Сүлжээнд $n$ ширхэг бичлэг болгоныг байршуулах буюу оруулах мөчийг бид мэднэ (энэ мөчөөс бүх серверүүд зэрэг ажиллаж эхэлнэ). Бүх бичлэгүүд ялгаатай мөчид сүлжээнд орж ирэх бөгөөд тэднийг орж ирсэн дарааллаар нь нягтруулан шахдаг. Хэрвээ бичлэг $s$ мөчид орж ирвэл, яг тэр мөчид үүний шахалт явагдаж эхлэх боломжтой. Хэрвээ бүх сервер ажиллаад завгүй байвал зарим бичлэгийн шахалт нь хүлээгддэг. Хэрвээ аль нэг сервер ажиллах боломжтой болвол шууд дараагийн бичлэгийг шахаж эхэлдэг. Шахагдах дарааллаа хүлээж буй бичлэгүүд дараалал үүсгэдэг. Бичлэгнүүд шахагдаж эхэлснээс хойш зарим серверүүд ажиллах боломжтой болвол нэн даруй хүлээлгэнд байгаа бичлэгийг шахаж эхэлдэг.
Бичлэг болгоны шахагдаж дуусах мөчийг олно уу.
Оролт
Эхний мөрөнд бичлэгийн тоо болон серверийн тоо болох 2 бүхэл тоонууд $n$ ба $k$ ($1 ≤ n, k ≤ 5*10^{5}$) өгөгдөнө.
Дараагийн $n$ ширхэг мөрөнд бичлэг болгоны тайлбарууд болох 2 бүхэл тоонууд $s_{i}, m_{i}$ ($1 ≤ s_{i}, m_{i} ≤ 10^{9}$) өгөгдөнө. Энд $s_{i}$ нь $i$ дэхь бичлэгийн сүлжээнд орж ирэх мөч. $m_{i}$ нь $i$ дэхь бичлэгийн урт минутаар өгөгдөнө. Энд бүх $s_{i}$--ууд хоорондоо ялгаатай бөгөөд $s_{i}$-ын ихсэх дарааллаар буюу сүлжээнд орж ирэх дарааллаараа өгөгдөнө.
Гаралт
$n$ ширхэг тоог $e_{1}, e_{2}, ..., e_{n}$ хэвлэнэ үү. Энд $e_{i}$ нь серверүүд ажиллаж эхэлснээс хойших $i$ дэхь бичлэг шахагдаж дуусах хугацаа (секундээр).
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
3 2 1 5 2 5 3 5
Гаралт
6 7 11
Оролт
6 1 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000 6 3
Гаралт
1000000001 2000000001 3000000001 4000000001 5000000001 5000000004