pillars

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

On a horizontal line, there are N uniformly spaced vertical pillars. The pillars are numbered 0 through N-1, in order. For each i, the distance between the bottoms of pillars i and i+1 is exactly w. For each i, the height of pillar i (0-based index) is an integer between 1 and heights[i], inclusive. We want to take a single piece of rope and use it to join the top ends of all pillars, in order. (Once in place, the rope will have the shape of a polyline consisting of N-1 segments.) What is the shortest length of rope that is guaranteed to be sufficient, regardless of the actual pillar heights?
 
You are given the vector heights and the int w. Compute and return the answer to the above question. In other words, find a sequence of pillar heights (within the given constraints) for which the length of the rope we need is maximized, and return that maximum.
Notes
-
Your return value must have a relative or an absolute error of less than 1e-9.
Constraints
-
heights will contain between 1 and 50 elements, inclusive.
-
Each element of heights will be between 1 and 100, inclusive.
-
w will be between 1 and 100, inclusive.

Input

 The first line is an integer n indicating the vector\'s size.then contains n integers.
netx line is w.

Output

For each test case, please print the answer maximum, The number must be written with exactly 6 digits after a decimal point

Sample Input

3 3 3 3
2
4 1 1 1 1
100

Sample Output

5.656854
300.000000

Hint

 

Source