题目描述
《神犇岛探险》是极其自虐的一款游戏。kAc浪费了无数人参之后,终于到了该游戏的奖励关。
奖励关是这样的:
有N个物品摆在kAc面前,按照顺序编号为1..n。第i个物品有价值a[i],价值可正可负。
kAc按照顺序依次经过这些物品。每经过一个物品的时候,他可以选择拿走或者不拿走。
kAc的初始体力值是1。每拿走一个物品后,他的体力值变为以前的k倍。(0 < k < 1)
为了增加难度,游戏规定:任意连续M个物品中,至少有一个要被拿走。
得分的计算方法:对于每一个拿走的物品,得分为该物品的价值*拿走该物品时的体力值。总得分为所有拿走物品的分数和。
请注意,第一个物品用以计算的体力值是1而不是k,第二个物品用以计算的体力值是k而不是k^2,...以此类推。
求他能得到的最高分。
对于30%:N <= 10
对于60%:N <= 1000
对于100%:N <= 100000, 1 <= M <= N ,所有物品的价值的绝对值<=10^9
时限:1s
内存限制:256MB
输入格式
第一行两个整数N,M
接下来一个实数k
接下来一行N个整数,分别表示这N个物品的价值。
输出格式
一个保留5位小数的实数,表示答案。
样例输入
样例输出