Нохойнд зориулсан нийгмийн сүлжээ 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$ дэхь бичлэг шахагдаж дуусах хугацаа (секундээр).