eolymp
Competitions

2019 Fall KBTU OPEN

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