CSES - Ositus
  • Time limit: 1.00 s
  • Memory limit: 128 MB
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$.