D. Discrete Fourier Transform
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a sequence of integer $$$f_0, f_1, \ldots, f_{n-1}$$$, the discrete Fourier transform gives a sequence of complex numbers $$$F_0, F_1, \ldots, F_{n-1}$$$ that

$$$$$$ F_t = \sum_{s=0}^{n-1} f_s\ e^{-2 \pi i s t / n}$$$$$$

for each $$$t=0,1,\ldots,n-1$$$, where $$$e^{i\theta} = \cos \theta + i \sin \theta$$$, and $$$i$$$ is the imaginary unit that $$$i^2=-1$$$.

You may reset $$$f_k$$$ to any integer value to minimize the maximum value among $$$|F_0|, |F_1|, \ldots, |F_{n-1}|$$$, where $$$|z|=|p+qi|=\sqrt{p^2+q^2}$$$ $$$(p, q \in \mathbb{R})$$$ is the modulus of the complex number $$$z$$$.

Input

The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 2\,000$$$) and $$$k$$$ ($$$0 \le k \lt n$$$).

The second line contains $$$n$$$ integers $$$f_0, f_1, \ldots, f_{n-1}$$$ ($$$-2\,000 \le f_i \le 2\,000$$$).

Output

Output a line containing a single real number, indicating the minimum of the maximum value among $$$|F_0|, |F_1|, \ldots, |F_{n-1}|$$$ after resetting $$$f_k$$$ to any integer value.

Your answer is acceptable if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, your output is accepted if and only if $$$\frac{|a - b|}{\max\{1, |b|\}} \leq 10^{-9}$$$.

Example
Input
3 2
1 1 0
Output
2.0