[SCOI2006]zh_tree

张老师根据工作需要，设计了一种特殊的二叉搜索树，并将其命名为 zh_tree。

一棵具有 $n$ 个结点的 zh_tree，其中序遍历恰好为 $(1,2,3,\ldots,n)$，数字 $1,2,3,\ldots,n$ 分别为各结点的编号。这 $n$ 个结点对应一组学术论文中出现的 $n$ 个不同单词。

第 $j$ 个单词在这组论文中出现的次数记为 $d_j$。例如，$d_2=10$ 表示第 $2$ 个结点所对应的单词在这组论文中出现了 $10$ 次。设这组论文中出现的单词总数为 $S$，则

$$S=d_1+d_2+\cdots+d_n。$$

记

$$f_j=\frac{d_j}{S}$$

为第 $j$ 个单词在这组论文中出现的概率，即出现频率。

张老师规定根结点的深度为 $0$。如果第 $j$ 个结点的深度为 $r$，则访问该结点的代价 $h_j$ 为

$$h_j=k(r+1)+c，$$

其中 $k,c$ 是已知的、不超过 $100$ 的正实数。

zh_tree 是满足上述中序遍历要求，并使平均访问代价

$$h_1f_1+h_2f_2+\cdots+h_nf_n$$

达到最小的二叉树。

请根据给定数据，求出访问 zh_tree 的最小平均代价。

输入格式

第一行包含三个用空格分隔的数 $n,k,c$。其中，$n$ 为正整数，$k,c$ 为正实数。

第二行包含 $n$ 个用空格分隔的正整数 $d_1,d_2,\ldots,d_n$，分别表示每个单词出现的次数。

输出格式

输出一行一个实数，保留 $3$ 位小数，表示访问 zh_tree 的最小平均代价。

样例输入

4 2 3.5
20 30 50 20

样例输出

7.000

数据范围

• $n\le 30$，且 $n$ 为正整数；
• $k,c\le 100$，且 $k,c$ 为正实数；
• $1\le d_j\le 200$，且 $d_j$ 为正整数。

来源与许可

本题为 SCOI 2006 试题「zh_tree」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 2 3.5
20 30 50 20

输出

7.000