Farmer John ist ein erstaunlicher Buchhaltungskünstler und merkt, dass ihm das Geld für die Farm ausgehen könnte. Er hat die genauen Ausgaben ($1 \le money_{i} \le 10,000$) für jeden der nächsten $N$ Tage ($1 \le N \le 100,000$) berechnet und notiert.

FJ plant einen Haushalt für genau $M$ aufeinanderfolgende Finanzperioden ($1 \le M \le N$), genannt „fajomonths“. Jede umfasst einen oder mehrere aufeinanderfolgende Tage; jeder Tag gehört zu genau einer Periode.

Er will die Perioden so einteilen, dass die Ausgaben der teuersten Periode minimal werden, und so seine Monatsgrenze bestimmen.

Eingabe

Zeile 1: zwei durch ein Leerzeichen getrennte ganze Zahlen $N$ und $M$. Zeilen $2\ldots N+1$: Zeile $i+1$ enthält Farmer Johns Ausgaben in Dollar an Tag $i$.

Ausgabe

Zeile 1: die kleinstmögliche Monatsgrenze, mit der Farmer John auskommen kann.

Beispiele

Eingabe 1

7 5
100
400
300
100
500
101
400

Ausgabe 1

500

Hinweis

Fasst er die ersten zwei Tage zu einem Monat, den dritten und vierten zu einem und jeden der letzten drei zu einem eigenen zusammen, zahlt er höchstens 500 Dollar pro Monat. Jede andere Einteilung ergibt eine größere minimale Monatsgrenze.

Aufgabenquelle: USACO, März 2007.