Description

农场主约翰的农场里有n(1 <= n <= 100,000)块场地排成一排。每块场地里都养着一定量的奶牛（1 <=奶牛数量<= 2000）。约翰想用栅栏将连续的几个场地围起来组成一个大的区域。约翰想让区域内的每个场地里的奶牛平均数最大。且每个区域内的场地数不得少于L（1 <= L <= n）。约翰需要你帮他计算栅栏区域内平均数的最大值。

Format

Input

第一行是用空格隔开的两个整数n和L。
第二行为n个用空格隔开的整数，其中第i个整数表示第i块场地里的奶牛数量。

Output

输出一个整数，即栅栏区域中每个场地的奶牛平均数量的最大值的1000倍（不用四舍五入，直接输出）。

Sample 1

Input

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

Output

6500

Limitation

1s, 30000KiB for each test case.