Farmer John jest zadziwiającym mistrzem rachunkowości i odkrył, że może zabraknąć pieniędzy na farmę. Obliczył i zapisał dokładne wydatki ($1 \le money_{i} \le 10,000$) na każdy z kolejnych $N$ dni ($1 \le N \le 100,000$).

FJ chce budżetu na dokładnie $M$ kolejnych okresów finansowych ($1 \le M \le N$), zwanych „fajomonths”. Każdy zawiera jeden lub więcej kolejnych dni; każdy dzień należy dokładnie do jednego okresu.

Chce podzielić okresy tak, aby zminimalizować wydatki najdroższego i ustalić miesięczny limit.

Wejście

Wiersz 1: dwie liczby całkowite $N$ i $M$ oddzielone spacją. Wiersze $2\ldots N+1$: wiersz $i+1$ zawiera dolary wydane przez Farmer John dnia $i$.

Wyjście

Wiersz 1: najmniejszy możliwy miesięczny limit Farmer John.

Przykład

Wejście 1

7 5
100
400
300
100
500
101
400

Wyjście 1

500

Uwagi

Jeżeli pierwsze dwa dni będą miesiącem, trzeci i czwarty kolejnym, a ostatnie trzy każdy osobnym, wyda najwyżej 500 dolarów miesięcznie. Każdy inny podział daje większy minimalny limit miesięczny.

Źródło zadania: USACO, marzec 2007.