Competitions

# Pretty necklace

Temirulan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of blue and red colored beads.

Temirulan already has one that consists of n beads. He knows that his girlfriend prefers red color over blue, so he decided to cut some subsequence of at least k beads from the original necklace such that the ratio between red ones and the number of chosen beads will be maximized.

Can you help him to find this maximum ratio?

#### Input

The first line contains two integers n, k (1kn5 * 105) - the number of beads on the thread and lower-bound of beads for the new necklace.

The second line contains the sequence of n integers separated by a single space ai (0ai1) - description of the original necklace.

ai = 0 corresponds to blue and ai = 1 corresponds to red color.

#### Output

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
8 4
11101110

Output example #1
0.857142448425

Input example #2
8 4
11011001

Output example #2
0.833333015442

Input example #3
10 4
1001001001

Output example #3
0.599999427795

Source 2019 Fall KBTU OPEN, Problem B