Cutting Straw Bundles

Kendo master Pidol will demonstrate straw bundle cutting in front of his juniors. There are N straws numbered 1 to N, and Pidol will perform an N-stage cut. Straw i is a rectangle with height H and width 1. An N-stage cut means cutting the bundle formed by placing these N straws side by side in numerical order without gaps, which is a rectangle with height H and width N.

A cut can be represented by a single straight line across the bundle. This line is called the cutting line. The cutting line must always pass through the left and right edges of the bundle. If the line passes through an endpoint of an edge, it still counts as passing through that edge.

Let the two top vertices of straw i be $A_i$ and $B_i$ from left to right, and let the points where the cutting line meets straw i be $D_i$ and $C_i$ from left to right. If the strength of straw i is $f_i$, the force needed to cut straw i is $f_i \times (\text{area of quadrilateral } A_iB_iC_iD_i)$. In some cases $A_i$ and $D_i$ coincide, or $B_i$ and $C_i$ coincide. Then the area is computed as the area of a triangle instead of a quadrilateral.

Pidol wants to show a 'great N-stage cut'. For an N-stage cut to count as great, the sum $\sum_{i=1}^{N} (\text{area of quadrilateral } A_iB_iC_iD_i)$ must be at least $S$. Find the minimum total force Pidol needs when he performs a great N-stage cut using the least force.

The first line contains integers $N$, $H$, and $S$ separated by spaces. $(1 \le N, H \le 10^5;\ 1 \le S \le NH)$

The second line contains integers $f_1, f_2, f_3, \dots, f_N$ separated by spaces. $(1 \le f_i \le 10^5)$

On the first line, print the minimum force needed for a great N-stage cut. An absolute or relative error of up to $10^{-4}$ is accepted.