Problem4459--「一本通 1.2 例 2」Best Cow Fences

4459: 「一本通 1.2 例 2」Best Cow Fences

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

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

Input

第一行输入整数 $n, L$。
接下来一行,输入 $n$ 个正整数。每个整数 $A_i$ 表示 $i$ 片区域内包含的牛的数目。

Output

一个整数,表示答案的 $1000$ 倍(不用四舍五入,直接输出)。

Constraints

$1 \leq n \leq 10^5,\ 0 \leq A_i \leq 2,000$

Sample 1 Input

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

Sample 1 Output

6500

Source/Category

提高算法 6.2.二分与三分