k altmassivə ayırma

$n$ elementdən ibarət massiv və $k$ ədədi verilir. Verilmiş massivi $k$ altmassivə ayırın (bütün elementlər iştirak etməlidir). Bütün $k$ altmassivin elementlərinin cəmləri arasında maksimunu hesablayın. Ayırmanı elə etmək lazımdır ki, bu maksimum qiymət minimum olsun. Bu maksimum qiyməti tapın.

Giriş verilənləri

İlk sətirdə iki $n$ və $k(n\le 10^6,1\le k\le n)$ tam ədədləri verilir. İkinci sətirdə hər biri $10^9$-u aşmayan $n$ natural ədəd verlir.

Çıxış verilənləri

Bütün $k$ sayda altmassivin elementlərinin cəmləri arasında mümkün maksimumların ən kiçiyini çap edin.

Nümunələr

Birinci nümunədə optimal ayırma $\{1,2\},\{3\},\{4\}$ olacaq. Bütün altmassivlərin elementlərinin cəmlərinin maksimumu $4$-dür, bu da $3$ altmassiv üçün ən kiçik qiymətdir.

İkinci nümunədə optimal ayırma $\{1,2,3,4\},\{2,3,4\},\{2,3,1\}$. Bütün altmassivlərin elementlərinin cəmlərinin maksimumu $10$-dur, bu da $3$ altmassiv üçün ən kiçik qiymətdir.