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.