AT_arc128_c [ARC128C] Max Dot

[problemUrl]: https://atcoder.jp/contests/arc128/tasks/arc128_c 整数 $ N,M,S $，及び長さ $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます． 次の条件をすべて満たす長さ $ N $ の非負**実数**列 $ x=(x_1,x_2,\cdots,x_N) $ を作ることを考えます． - $ 0\ \leq\ x_1\ \leq\ x_2\ \leq\ \cdots\ \leq\ x_N\ \leq\ M $ - $ \sum_{1\ \leq\ i\ \leq\ N}\ x_i=S $ ここで，$ x $ のスコアを $ \sum_{1\ \leq\ i\ \leq\ N}\ A_i\ \times\ x_i $ と定義します． $ x $ のスコアとしてありうる最大の値を求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ S $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ． 絶対誤差または相対誤差が $ 10^{-6} $ 以内であれば，正解と判定される．

### 制約 - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ M\ \leq\ 10^6 $ - $ 1\ \leq\ S\ \leq\ \min(N\ \times\ M,10^6) $ - $ 1\ \leq\ A_i\ \leq\ 10^6 $ - 入力される値はすべて整数である ### Sample Explanation 1 $ x=(0,1,2) $ とするのが最適です． ### Sample Explanation 2 $ x=(2/3,2/3,2/3) $ とするのが最適です．