#P18095. Lottery

Lottery

Lottery

题目描述

奖池中有 nn 件物品,第 ii 件的价值为 AiA_i。你必须至少抽奖一次。

每轮先支付当前费用 cc,再等概率抽到 nn 件物品中的一件。看到结果后,可以保留该物品并结束,也可以放弃该物品并进入下一轮;放弃后,下一轮费用变为 c+kc+k。各轮抽取相互独立,奖池不减少。

最终收益等于最后保留的物品价值减去所有轮次支付的费用。选择使期望收益最大的策略,求最大期望收益。

输入格式

第一行三个整数 n,c,kn,c,k。第二行 nn 个整数 A1,…,AnA_1,\ldots,A_n。

输出格式

输出一个实数。与正确答案的绝对误差或相对误差不超过 10−610^{-6} 即可。

数据范围

1≤n,c,Ai≤4×1051\le n,c,A_i\le4\times10^5,0≤k≤4×1050\le k\le4\times10^5。

样例 1

输入

3 2 0
4 1 6

输出

2.000000000

样例 2

输入

9 8 2
53 71 5 6 80 37 50 33 90

输出

51.557786840