Aquarium

problem

AOR Ika got a water tank with a size of $1$ in length and $N$ in width. The aquarium is tall enough to hold water. The aquarium has $N-1$ partitions and is evenly spaced into $N$ compartments. When water was poured here, the height of the water in each section became $a_i$.

AOR Ika decided to remove some dividers and reduce the number of compartments to $M$ or less. When you have removed the dividers, find the maximum sum of the water heights in each compartment.

The thickness of the partition can be ignored.

input

$N \ M$ $a_1 \ cdots a_N$

output

Output the maximum value of the total water height of each section in one line. Also, output a line break at the end. It is acceptable if the relative or absolute error is less than or equal to $10 ^ {-6}$.

Example

Input

5 3 9 1 2 3 9

Output

20.000000

inputFormat

input

$N \ M$ $a_1 \ cdots a_N$

outputFormat

output

Output the maximum value of the total water height of each section in one line. Also, output a line break at the end. It is acceptable if the relative or absolute error is less than or equal to $10 ^ {-6}$.

Example

Input

5 3 9 1 2 3 9

Output

20.000000

样例

5 3
9 1 2 3 9

20.000000