32134번 - 짚단 베기 스페셜 저지

문제

검도왕 피돌이는 후배들 앞에서 짚단 베기를 선보일 예정이다. 짚단은 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}$까지 허용한다.

제한

힌트