짚단 베기

검도 고수 피돌이는 후배들 앞에서 짚단 베기를 선보일 예정이다. 짚단은 1번부터 N번까지 총 N개가 있고, 피돌이는 짚단 N단 베기를 한다. i번 짚단은 높이가 H이고 너비가 1인 직사각형이다. 짚단 N단 베기는 이 짚단 N개를 번호 순서대로 빈틈없이 붙여서 만든, 높이가 H이고 너비가 N인 직사각형 짚단 묶음을 베는 것을 뜻한다.

베기는 짚단 묶음 위의 직선 하나로 나타낼 수 있으며, 이 직선을 베기 직선이라 한다. 베기 직선은 항상 짚단 묶음의 왼쪽 변과 오른쪽 변을 지나야 한다. 직선이 어떤 변의 끝점을 지나면, 그 변을 지난 것으로 본다.

i번 짚단의 위쪽 두 꼭짓점을 왼쪽부터 차례로 $A_i$, $B_i$라 하고, i번 짚단과 베기 직선이 만나는 교점을 왼쪽부터 차례로 $D_i$, $C_i$라 하자. i번 짚단의 강도를 $f_i$라 하면, i번 짚단을 베는 데 드는 힘은 $f_i \times (\text{사각형 } A_iB_iC_iD_i\text{의 넓이})$이다. 경우에 따라 $A_i$와 $D_i$가 겹치거나 $B_i$와 $C_i$가 겹칠 수 있다. 이때는 사각형 대신 삼각형의 넓이로 계산한다.

피돌이는 '멋진 N단 베기'를 선보이려 한다. N단 베기가 멋진 베기가 되려면 $\sum_{i=1}^{N} (\text{사각형 } A_iB_iC_iD_i\text{의 넓이})$가 $S$ 이상이어야 한다. 피돌이가 멋진 N단 베기를 가장 적은 힘으로 벤다고 할 때, 필요한 힘의 합을 구하여라.

첫째 줄에 정수 $N$, $H$, $S$가 공백으로 구분되어 주어진다. $(1 \le N, H \le 10^5;\ 1 \le S \le NH)$

둘째 줄에 정수 $f_1, f_2, f_3, \dots, f_N$이 공백으로 구분되어 주어진다. $(1 \le f_i \le 10^5)$

첫째 줄에 멋진 N단 베기를 할 때 드는 최소 힘을 출력하라. 절대 오차 또는 상대 오차는 $10^{-4}$까지 허용한다.