#6697. 农场养牛

农场养牛

问题描述

Mibbp的农场有 NN 块田地,由于Mibbp很喜欢牛(看头像都看得出来),所以放着田地不种菜去养牛,每块地牛的数量为aia_i

Mibbp想把一部分连续的田地圈起来,并使得圈起来的田地中包含的牛的数量的平均值达到最大。

圈起区域内至少需要包含 FF 块地

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

输入

第一行输入整数 NNFF,数据间用空格隔开。

接下来 NN 行,每行输入一个整数aia_i,表示第 ii 片区域内包含的牛的数目。

输出

输出一个整数,表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。

样例

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

提示

样例1解释

第 4 块区域到底9块区域平均值为6.5,乘1000再向下取整为6500

数据范围

  • 1N1000001 \leq N \leq 100000
  • 1FN 1 \leq F \leq N
  • 1ai20001 \leq a_i \leq 2000