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 (1 ≤ k ≤ n ≤ 5 * 10^5) - 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 a[i] (0 ≤ a[i] ≤ 1) - description of the original necklace.
a[i] = 0 corresponds to blue and a[i] = 1 corresponds to red color.