AT_past202303_k 金貨と袋のゲーム

Takahashi and Aoki are playing a game with $ N $ rounds. For $ i=1,\ldots,N $ , the $ i $ -th round consists of the following steps in the order from top to bottom. - If $ i \geq 2 $ and Takahashi received a penalty in the $ (i-1) $ -th round, the $ i $ -th round ends without performing the steps below. - Takahashi is dealt $ a_i $ gold coins. - Takahashi does one of the following actions. - Put $ \left \lfloor \frac{a_i \times t}{100} \right \rfloor $ gold coins into a bag and show it to Aoki. ( $ \lfloor x \rfloor $ is the greatest integer not exceeding $ x $ .) Here, it is guaranteed that $ \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1 $ . - Show an empty bag to Aoki. - Aoki chooses an integer $ x $ between $ 1 $ and $ 100 $ , inclusive, with equal probability. - If $ x\leq p $ , he examines the bag. If it contains no gold coins, Takahashi puts $ \left \lfloor \frac{a_i \times t}{100} \right \rfloor $ gold coins into the bag and receives a penalty. - If $ x \gt p $ , he does nothing. - Takashi earns all gold coins dealt in this round that are not in the bag now. Here, Aoki chooses $ x $ independently in each round. Takahashi will make his choice in each round to maximize the expected value $ E $ of the total number of gold coins earned in all $ N $ rounds. Find this maximized value of $ E $ .

The input is given from Standard Input in the following format: > $ N $ $ t $ $ p $ $ a_1 $ $ \ldots $ $ a_N $

Print the answer. Your output is considered correct if its absolute or relative error from the true answer is at most $ 10^{−6} $ .

### Sample Explanation 1 Here is a way for Takahashi to maximize the expected value of the total number of gold coins earned. - In the first round, put nothing into the bag. - In the second round, put the specified number of gold coins into the bag (if he did not receive a penalty in the first round). - In the third round, put nothing into the bag. ### Sample Explanation 2 The true answer to this input is $ 570.9 $ . The above output is not identical to this value, but the error is small enough to be considered correct. ### Constraints - $ 1 \leq N \leq 100 $ - $ 1 \leq t,p \leq 99 $ - $ 1 \leq a_i \leq 10^9 $ - $ \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1 $ - All values in the input are integers.