#14. 最佳牛围栏

最佳牛围栏

题目描述

农夫约翰的农场由 N\red{N} 块田地组成,每块地里都有一定数量的牛,其数量不会少于1\red{1}头,也不会超过2000\red{2000}头。

约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 F\red{F} 块地,其中 F\red{F} 会在输入中给出。

在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 N\red{N}F\red{F} ,数据间用空格隔开。

接下来 N\red{N} 行,每行输出一个整数,第i+1\red{i+1}行输出的整数代表,第i\red{i}片区域内包含的牛的数目。

输出格式

输出一个整数,表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000\red{1000}得到的数值。

样例

输入数据

10 6
6 
4
2
10
3
8
5
9
4
1

输出数据

6500

提示

1N100000\red{1≤N≤100000}

1FN\red{1≤F≤N}