Optimal Zh_Tree Construction

Professor Zhang needs to design a special binary search tree called zh_tree for his work. This tree has exactly n nodes whose in‐order traversal is exactly \( (1,2,3,\ldots,n) \). Each node corresponds to a unique word in a set of academic papers. For the j-th word, let \( d_j \) denote the number of times it appears in the papers. Let \( S=d_1+d_2+\cdots+d_n \) be the total number of word appearances, and define the frequency \( f_j=\frac{d_j}{S} \).

The cost to access a node is determined by its depth. The depth of the root is 0 and if the j-th node is at depth \( r \), then its access cost is given by \[ h_j=k(r+1)+c, \] where \( k \) and \( c \) are given positive integers (\( \le 100 \)). The average access cost of the tree is defined as \[ \text{Average Cost}=h_1f_1+h_2f_2+\cdots+h_nf_n. \] The zh_tree must be constructed so that this average cost is minimized.

Note: Since \( f_j=\frac{d_j}{S} \) and \( S \) is a constant, minimizing the average cost is equivalent to minimizing the weighted sum
\[ \sum_{j=1}^{n}d_j\cdot (\text{depth}(j)+1). \]

This is essentially the well known Optimal Binary Search Tree problem. The optimal recursive formulation is:

[ dp(i,j)=\begin{cases} 0, & i>j \ \left( \sum_{k=i}^{j} d_k \right) + \min_{r=i}^{j} (dp(i, r-1)+dp(r+1,j)), & i\le j \end{cases} ]

The final answer (the minimized average access cost) is computed as:

[ \text{Answer} = \frac{k\cdot dp(1,n)+c\cdot S}{S}. ]

Input/Output instructions are given below.

inputFormat

The input consists of three lines:

1. The first line contains a single integer n (the number of nodes, \( n \ge 1 \)).
2. The second line contains n space-separated positive integers \( d_1, d_2, \ldots, d_n \) (the frequencies counts for the corresponding nodes).
3. The third line contains two space-separated integers k and c (\( 1 \le k,c \le 100 \)).

outputFormat

Output a single line containing the minimized average access cost. The result should be printed as a floating point number rounded to three decimal places.

sample

3
1 2 3
2 1

4.333