Sinulle on annettu taulukko, jossa on n positiivista kokonaislukua.

Tehtäväsi on osittaa taulukko k väliin niin, että suurin välin summa on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja k: taulukon koko ja osituksen koko.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin välin summa.

Rajat

• 1 \le n \le 10^5
• 1 \le k \le n
• 1 \le x_i \le 10^9

Esimerkki

Syöte:

5 3
2 4 7 3 5

Tuloste:

8

Selitys: Paras ositus 3 osaan on [2,4],[7],[3,5], jossa välien summat ovat 6,7,8. Suurin summa on viimeisen välin summa 8.