问题 C: Is it rated?

Isn't it frustrating when a contest round where you've excelled is declared unrated? This may happen due to incorrect problems, long queues, server issues, or simply because some participants disliked the round?!  Post: "I'm speechless. (Since last month) there have been four rounds; I've participated in three, and two were unrated." You suspect a conspiracy: a ruthless, dark hand manipulates the rating system to favor certain individuals. Imagine you are this manipulator, but also a contestant on the Qniversal Cup contest platform. You intend to use the power of making rounds unrated to boost your ratings. There are $n$ contests, and your performance in each contest is denoted by $p_i$. You can issue up to $m$ apology announcements, each making a round unrated while all the other contests remain rated. The final rating is calculated as follows: - Start with the initial rating $r_0$: $r \gets r_0.$ - For each rated contest $i$ in increasing order, update the rating as a weighted average of the old rating and the performance: $r \gets k \cdot p_i + (1 - k) \cdot r,$ where $k$ is a predetermined update coefficient. Your goal is to maximize your final rating. Determine the highest possible rating you can achieve after making at most $m$ rounds unrated. Although the ratings displayed on contest platforms are usually integers, you know that internally, ratings are calculated using real numbers. Therefore, you need to report the real rating, accurate up to an absolute or relative error of $10^{-9}$.

The first line contains a single integer $T~ (1 \leq T \leq 1000)$, denoting the number of test cases. For each test case, there are three lines: \* The first line contains two integers $n, m ~ (1 \leq m \leq n \leq 10^5)$ and a real number $k ~ (0.1 \leq k \leq 1)$, where $n$ is the number of contests, $m$ is the maximum number of apology announcements you can make, and $k$ is the update coefficient with up to $3$ digits after the decimal point. \* The second line contains a single integer $r_0 ~ (0 \leq r_0 \leq 10 ^ 5)$, denoting the initial rating. \* The third line contains $n$ integers, $p_1, p_2, \dots, p_n ~ (0 \leq p_i \leq 10^5)$, representing your performance in each contest. It is guaranteed that the sum of $n$ among all $T$ cases will not exceed $3 \times 10 ^ 5$.

For each test case, output a single real number representing the highest possible rating you can achieve, which should be printed in decimal form and have at most $20$ digits after the decimal point. Your answer will be accepted if it is within an absolute or relative error of $10^{-9}$.