M. Mid Clocking
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

We have a number of processor slots in a row. The processors are each dedicated to a single task that they can complete before going into a busy-looping mode while they wait for the next instruction.

A processor can run at 100% speed if it has enough cooling, and that requires there be no adjacent processor. If a processor has 1 adjacent processor, it only runs at 60% of maximum speed. If it has 2 adjacent processors it can only run at 30% of maximum speed.

Illustration of Sample Input 2.

We know how many seconds each task will take running on a processor at full speed, starting from $$$t=0$$$, and need to allocate tasks to processors to ensure the last task finishes as soon as possible.

Input
  • The number of tasks to run, $$$n$$$, and the number of processor slots, $$$s$$$ ($$$1 \le n \le s \le 10^6$$$).
  • $$$n$$$ further integers giving the duration of each task $$$t_i$$$ in seconds if performed at 100% speed ($$$1 \le t_i \le 10^9$$$).
Output

Output the minimum time by which all of the tasks can be finished.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
4 5
1 1000 1 1
Output
1000
Input
7 10
5 2 3 5 4 6 7
Output
8.33333333