Problem C: Best Cow Fences

Problem C: Best Cow Fences

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 13  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

农夫约翰的农场由 N块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F块地,其中 F 会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。


Farmer John’s farm consists of N plots of land, and each plot contains a certain number of cow, no less than 1, and no more than 2,000.

John hopes to fence a part of the continuous field and maximize the average number of cattle contained in each plot in the fenced area.

The enclosed area must contain at least F plots, where F will be given in the input.

Under given conditions, calculate the average possible maximum value of the number of cattle contained in each plot in the enclosed area.

Input

第一行输入整数 N  F ,数据间用空格隔开。
接下来 N 行,每行输出一个整数,第i+1行输出的整数代表,第i片区域内包含的牛的数目。


The first lines inputs the integers N and F, and separated with spaces.

In the next N lines, each line outputs an integer. The integer output in the i+1th line represents the number of cattle contained in the i-th slice.

Output

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


Output an integer, which represents the maximum value of the average value of the number of cattle contained in each plot of land in the enclosed area, multiplied by 1000.


Sample Input Copy

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

Sample Output Copy

6500