{"raw_statement":[{"iden":"problem statement","content":"Given are integers $N$, $M$, $S$, and a sequence of $N$ integers $A=(A_1,A_2,\\cdots,A_N)$.\nConsider making a sequence of $N$ non-negative **real** numbers $x=(x_1,x_2,\\cdots,x_N)$ satisfying all of the following conditions:\n\n*   $0 \\leq x_1 \\leq x_2 \\leq \\cdots \\leq x_N \\leq M$,\n*   $\\sum_{1 \\leq i \\leq N} x_i=S$.\n\nNow, let us define the score of $x$ as $\\sum_{1 \\leq i \\leq N} A_i \\times x_i$. Find the maximum possible score of $x$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $1 \\leq M \\leq 10^6$\n*   $1 \\leq S \\leq \\min(N \\times M,10^6)$\n*   $1 \\leq A_i \\leq 10^6$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $S$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3 2 3\n1 2 3"},{"iden":"sample output 1","content":"8.00000000000000000000\n\nThe optimal choice is $x=(0,1,2)$."},{"iden":"sample input 2","content":"3 3 2\n5 1 1"},{"iden":"sample output 2","content":"4.66666666666666666667\n\nThe optimal choice is $x=(2/3,2/3,2/3)$."},{"iden":"sample input 3","content":"10 234567 1000000\n353239 53676 45485 617014 886590 423581 172670 928532 312338 981241"},{"iden":"sample output 3","content":"676780145098.25000000000000000000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}