Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3694

Time Limit: 10 Seconds      Memory Limit: 65536 KB

There are N (1 ≤ N ≤ 100000) soldiers stand in a line. Each soldier has a ability assessment value Vi (-10^8 ≤ Vi ≤ 10^8).

July want to select some soldiers into M (1 ≤ M ≤ 10) teams, each team consist of some soldiers standing consecutively. And its size should be between [L,R](inclusively and 1 ≤ L ≤ R ≤ N). Notice that each selected soldier can belong exactly one team.

Now your task is to maximize the average ability value of selected soldiers.


The input will consist of about 100 testcases.

The first line of one testcase is four integer N, indicating the amount of soldiers, M, indicating the required amount of teams, and [L,R] ,the size limit of each team.

following is N integers, the ability value of each soldier.


Each testcase should output exactly 1 lines, each line a float legal answer with two decimal places reserved. Output "-1"(without quotation) if there is no legal arrangement.

Sample Input

6 2 2 3
3 1 3 1 1 3

1 2 1 1

Sample Output



No matter you answer is 1.009 or 1.002, you should output 1.00 both to make the answer legitimate.

Author: CHEN, Cong
Contest: ZOJ Monthly, March 2013
Submit    Status