#1669. 小奇探险

小奇探险

题目描述

小奇去遗迹探险,遗迹里有 NN 个宝箱,有的装满了珠宝,有的装着废品。

小奇有地图,所以它知道每一个宝箱的价值,但是它不喜欢走回头路,所以要按顺序拿这 NN 个宝箱中的若干个。

拿宝箱很累的。一开始小奇的体力是 11,每得到一个宝箱之后,小奇得到的价值是体力 ×\times 宝箱的价值,之后它的体力就会变为原来的 kk(0<k<1)(0<k<1)

小奇不喜欢连续放过很多宝箱,所以任意一段长度为 MM 的序列中,小奇一定要取走其中的一个宝箱。

现在小奇想知道它能得到的最大价值和。

输入格式

第一行,两个整数 N,MN,M,表示的含义如题目中所述;

第二行,一个小数 kk,表示的含义如题目中所述,最多 44 位小数;

第三行,NN 个整数,第 ii 个整数表示第 ii 个宝箱的价值。

输出格式

输出一行,一个实数,表示小奇能得到的最大价值和,四舍五入保留两位小数。

样例

3 2
0.1
1 2 3
2.30

数据范围与提示

对于 30%30\% 的数据,有 1N101\le N\le 10
对于 60%60\% 的数据,有 1N10001\le N\le 1000
对于 100%100\% 的数据,有 1N1000001\le N\le 1000001MN1\le M\le N0<k<10<k<1109-10^9\le 所有宝箱的价值 109\le 10^9
本题版权归 Trinkle23897 所有