Muallif: __thecrash__

B. GPU navbati

Vaqt limiti: 1000 ms Xotira limiti: 256 mb

Startap kompaniyaning serverida \(m\) ta GPU (videokarta) bor. Dasturchilar serverga \(n\) ta hisoblash vazifasini navbatga qo'yishdi, \(i\)-vazifa istalgan GPU da roppa-rosa \(t_i\) daqiqa davom etadi. Har bir GPU bir vaqtda faqat bitta vazifani bajara oladi.

Vazifalar navbatdagi tartibda ishga tushiriladi. \(0\)-daqiqada bo'sh GPU lar navbatning boshidagi vazifalarni oladi. Keyin qaysidir GPU bo'shashi bilan u darhol navbatdagi keyingi vazifani oladi. Agar bir vaqtning o'zida bir nechta GPU bo'shasa, ular navbatdagi vazifalarni ketma-ket oladi.

Barcha vazifalar nechanchi daqiqada tugashini aniqlang.


Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n, m \le 2 \cdot 10^5\)) mos ravishda vazifalar soni va GPU lar soni.

Ikkinchi qatorda \(n\) ta butun son \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^9\)), vazifalarning davomiyligi navbatdagi tartibda.


Chiquvchi ma'lumotlar

Oxirgi vazifa tugaydigan daqiqani chiqaring.

Misollar

# Input.txt Output.txt
1
5 2
3 1 4 1 5
9
2
3 5
2 7 1
7
3
4 1
1 2 3 4
10

Izoh

Birinchi misolda 0-daqiqada birinchi GPU 3 daqiqalik vazifani, ikkinchi GPU 1 daqiqalik vazifani oladi. 1-daqiqada ikkinchi GPU bo'shaydi va 4 daqiqalik vazifani oladi, u 5-daqiqada tugaydi. 3-daqiqada birinchi GPU bo'shaydi va 1 daqiqalik vazifani oladi, u 4-daqiqada tugaydi. Shundan keyin birinchi GPU oxirgi 5 daqiqalik vazifani oladi, u 9-daqiqada tugaydi.

Ikkinchi misolda GPU lar vazifalardan ko'p, hamma vazifa birdaniga boshlanadi.

Uchinchi misolda bitta GPU bor, vazifalar birin-ketin bajariladi.

Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.

Navbatdagi musobaqa

Biriktirilgan musobaqa

SamCoding Round 11 (Div. 1)

Natijalar