Farmer John est un extraordinaire expert comptable et réalise qu'il risque de manquer d'argent pour la ferme. Il a calculé et noté exactement les dépenses ($1 \le money_{i} \le 10,000$) de chaque jour des $N$ prochains jours ($1 \le N \le 100,000$).

FJ veut établir un budget pour exactement $M$ périodes fiscales successives ($1 \le M \le N$), appelées « fajomonths ». Chacune contient un ou plusieurs jours consécutifs, et chaque jour appartient à exactement une période.

Il veut organiser les périodes pour minimiser les dépenses de celle qui dépense le plus, déterminant ainsi sa limite mensuelle.

Entrée

Ligne 1 : deux entiers séparés par un espace, $N$ et $M$. Lignes $2\ldots N+1$ : la ligne $i+1$ donne les dollars dépensés par Farmer John le jour $i$.

Sortie

Ligne 1 : la plus petite limite mensuelle possible pour Farmer John.

Exemples

Entrée 1

7 5
100
400
300
100
500
101
400

Sortie 1

500

Remarque

En regroupant les deux premiers jours, puis les troisième et quatrième, et en faisant un mois distinct pour chacun des trois derniers, il dépense au plus 500 dollars par mois. Toute autre organisation donne une limite mensuelle minimale plus grande.

Source du problème : USACO, mars 2007.