Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
124 - ZOJ Monthly, March 2013 - I
Arrangement

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.

Input

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.

Output

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
1

Sample Output

2.20
-1

Hint

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


Author: CHEN, Cong
Submit    Status