짚단 베기

검도왕 피돌이는 후배들 앞에서 짚단 베기를 선보일 예정이다. 짚단은 $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 (\square A\_i B\_i C\_i D\_i$의 넓이$)$이다. 특수한 경우 $\square A\_i B\_i C\_i D\_i$에서 $A\_i$와 $D\_i$가 겹치거나 $B\_i$와 $C\_i$가 겹칠 수 있다. 이때는 사각형의 넓이가 아닌 삼각형의 넓이로 계산한다.

피돌이는 후배들에게 멋진 모습을 보이기 위해 '멋진 $N$단 베기'를 선보이려 한다. '멋진 $N$단 베기'를 하기 위해서는 $N$단 베기를 했을 때 $\sum\_{i=1}^{N} (\square A\_i B\_i C\_i D\_i$의 넓이$)$가 $S$ 이상이어야 한다. 피돌이가 '멋진 $N$단 베기'를 선보일 때 가장 적은 힘이 들도록 벤다면 힘이 얼마나 필요한지 구하여라.

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

둘째 줄에 정수 $f\_1$, $f\_2$, $f\_3$, $\dots$, $f\_N$이 공백으로 구분되어 주어진다. $(1 \le f\_i \le 10^5)$

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