Farmer John è un sorprendente mago della contabilità e si accorge che può finire i soldi per la fattoria. Ha calcolato e annotato esattamente le spese ($1 \le money_{i} \le 10,000$) per ciascuno dei prossimi $N$ giorni ($1 \le N \le 100,000$).

FJ vuole un budget per esattamente $M$ periodi fiscali successivi ($1 \le M \le N$), chiamati «fajomonths». Ciascuno contiene uno o più giorni consecutivi, e ogni giorno appartiene a esattamente un periodo.

Vuole organizzare i periodi per minimizzare la spesa del periodo più costoso e determinare il limite mensile.

Input

Riga 1: due interi separati da uno spazio: $N$ e $M$. Righe $2\ldots N+1$: la riga $i+1$ dà i dollari spesi da Farmer John nel giorno $i$.

Output

Riga 1: il minimo limite mensile possibile con cui Farmer John può vivere.

Esempi

Input 1

7 5
100
400
300
100
500
101
400

Output 1

500

Nota

Se i primi due giorni formano un mese, il terzo e quarto un altro, e ciascuno degli ultimi tre un mese proprio, spende al massimo 500 dollari al mese. Ogni altra suddivisione dà un limite mensile minimo maggiore.

Fonte del problema: USACO, marzo 2007.