算法设计与分析

Sample - Enumeration

枚举典型题(4)- 河里面的石头

题目描述

有一条河,河中间有一些石头,已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头,问最多移除m块石头后(首尾两块石头不可以移除),相邻两块石头之间的距离的最小值最大是多少。

输入格式

多组输入(<=20组数据,读入以EOF结尾)

每组第一行输入两个数字,n(2<=n<=1000)为石头的个数,m(0<=m<=n-2)为可移除的石头数目

随后n-1个数字,表示顺序和相邻两块石头的距离d(d<=1000)

输出格式

每组输出一行结果,表示最大的点数

样例输入

4 1 1 2 3

样例输出

3