Masala B
Ko'prikdan o'tish
Osma ko‘prik chuqur darani kesib o‘tadi. Odamlar ko‘prikdan guruh bo‘lib o‘tishlari mumkin, ammo ko'prik juda ham eski bo'lganligi uchun, hammani bir vaqtda ko'tara olmaydi, boshqa so'zlar bilan aytganda bir vaqtda ko'prikdan faqatgina 1 ta guruh o'tishi mumkin va guruhdagi odamlar soni M tadan oshmasligi kerak. Guruhning ko‘prikdan o‘tish vaqti shu guruhdagi eng sekin odamning tezligiga bog‘liq. Siz ko‘prik xavfsizligi uchun mas’ulsiz va guruhlarning o‘tishini nazorat qilasiz.
Odamlar navbatda turishgan; oldingi guruh o‘tib bo‘lgach, siz navbatdagi bir necha kishiga “endi o‘tishingiz mumkin” deb ruxsat berasiz. Guruhlar turli hajmda bo‘lishi mumkin, lekin hech bir guruhda M tadan ortiq odam bo‘lmasligi shart. Maqsad — odamlarning tartibini buzmasdan, hammani eng qisqa umumiy vaqt ichida ko'prikdan o‘tkazishdir.
Kirishning birinchi qatorida bitta butun son \(T\) - testlar soni kiritiladi. Har bir test quyidagi formatda kiritiladi:
- Birinchi qatorda \(N\) hamda \(M\) - odamlar soni hamda guruh uchun cheklov qiymati kiritiladi.
- Keyingi qatorda N ta butun son - har bir odamning ko'prikdan o'tish vaqti kiritiladi. Bunda 1 - son, navbat boshida turgan insonga, N - son esa navbat oxiridagi odamga to'g'ri keladi.
\(1 \le T \le 10^4\)
\(1 \le N \le 10^5\)
\(1 \le M \le min(100, N)\)
\(N\) ning barcha testlardagi umumiy qiymati \(5 \times 10^5\) dan oshmaydi
Har bir test uchun, alohida qatorda bitta butun son, hamma odam ko'prikdan xavfsiz o'tishi uchun minimal qancha vaqt ketishini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 2 1 2 3 4 5 4 3 5 1 2 6 6 3 3 3 3 3 3 3 |
9 11 6 |
Telegram kanalimizga obuna bo'ling