Muallif: __thecrash__

F. Alkimyogar yordamchilari

Vaqt limiti: 1000 ms Xotira limiti: 256 mb

Minora qulashidan oldin, alkimyogar qatorda tizilgan \(n\) ta kristallni (\(a_1, a_2, \dots, a_n\) tartibida, energiyalari mos ravishda) \(m\) ta yordamchisiga taqsimlab berishi kerak. Har bir yordamchi kristallarning ketma-ket (tartibni buzmasdan) bo'lagini oladi — ya'ni massiv aynan \(m\) ta bo'sh bo'lmagan qismga bo'linadi.

Alkimyogar adolatli bo'lishni xohlaydi: eng ko'p energiya olgan yordamchining yukini iloji boricha kamroq qilishni istaydi. Eng kichik mumkin bo'lgan maksimal yukni toping.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi (\(1 \le m \le n \le 2 \times 10^5\)).

Ikkinchi qatorda \(n\) ta butun son \(a_1, \dots, a_n\) beriladi (\(1 \le a_i \le 10^9\)) — kristallarning energiyalari.

Chiquvchi ma'lumotlar

Eng kichik mumkin bo'lgan maksimal yukni chop eting.

Misollar

1

5 2
7 2 5 10 8

18

2

5 3
7 2 5 10 8

14

3

7 4
4 8 9 2 3 6 5

12

Izoh

1-Test: \(n=5\), \(m=2\), kristallar: \(7, 2, 5, 10, 8\)
Massivni \(2\) ta ketma-ket bo'lakka bo'lamiz: \([7, 2, 5]\) (yig'indi = \(14\)) va \([10, 8]\) (yig'indi = \(18\)). Ikki bo'lakning maksatli maximumi = \(18\). Boshqa har qanday bo'linish bundan kattaroq yuk beradi, shuning uchun eng kichik maksimal yuk = \(18\).

2-Test: \(n=5\), \(m=3\), xuddi shu kristallar
Endi \(3\) ta bo'lakka bo'lamiz: \([7, 2, 5]\) (\(14\)), \([10]\) (\(10\)), \([8]\) (\(8\)). Maksimal yuk = \(14\). Bo'laklar soni oshgani sari yukni tekislash osonlashadi, shuning uchun javob kamaydi (\(18 \rightarrow 14\)).

3-Test: \(n=7\), \(m=4\), kristallar: \(4, 8, 9, 2, 3, 6, 5\)
Optimal bo'linish maksimal yukni \(12\) ga tushiradi. Undan kichik limit bilan bo'lib bo'lmaydi, chunki \(9\) o'zi katta element bo'lib, kamida bitta guruh yukini \(12\) ga yetkazadi.