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
Сэтгэгдлүүдийг ачааллаж байна...