程程的生活费

题目描述

程程是一个聪明的中学生，在学校住宿。他敏锐的意识到自己要破产了，因为预计的生活费很难坚持到学期末了。他又不想重新跟妈妈要钱，程程想用学过的知识来解决问题，所以他计算并记录下了接下来 $N (1≤N≤100,000)$ 天里每天需要的花费。 程程打算为连续的 $M (1≤M≤N)$ （到期末）个财政周期创建预算案，他把一个财政周期重新命名为 $pr$ 月。每个 $pr$ 月包含一天或连续的多天，每天被恰好包含在一个 $pr$ 月里。 程程的目标是合理安排每个 $pr$ 月包含的天数，使得花费最多的 $pr$ 月的花费尽可能少。

输入格式

第一行包含两个整数 $N,M$，用单个空格隔开。 接下来 $N$ 行，每行包含一个 $1$ 到 $10000$ 之间的整数，按顺序给出接下来 $N$ 天里每天的花费。

输出格式

一个整数，即最大月度花费的最小值。

7 5
100
400
300
100
500
101
400

500

提示

观察样例数据，如果程程将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大pr月花费为500。其他任何分配方案都会比这个值更大。

来源

童程童美