AT_abc402_e [ABC402E] Payment Required

In the year 30XX, each submission to a certain contest requires a payment. The contest has $ N $ problems. Problem $ i $ has $ S_i $ points, and each submission costs $ C_i $ yen. When Takahashi submits to the $ i $ -th problem, he solves it with probability $ P_i $ %. Each submission’s outcome is independent of the others. He has $ X $ yen. He cannot make any submission that would cause his total spending to exceed $ X $ yen. Find the expected value of the total score of the problems he solves when he chooses submissions to maximize this value. He may decide which problem to submit to next after seeing the result of the previous submission, and solving the same problem more than once awards the same score as solving it once.

The input is given from Standard Input in the following format: > $ N $ $ X $ $ S_1 $ $ C_1 $ $ P_1 $ $ S_2 $ $ C_2 $ $ P_2 $ $ \vdots $ $ S_N $ $ C_N $ $ P_N $

Print the answer. Your output is considered correct if its absolute or relative error does not exceed $ 10^{-6} $ .

### Sample Explanation 1 Consider the following submission strategy: - First, submit to the 1st problem. - If that submission is correct, submit to the 2nd problem; otherwise, submit again to the 1st problem. The expected total score for this strategy is $ 95 $ points. No strategy can exceed an expected score of $ 95 $ , so print $ 95 $ . ### Constraints - $ 1 \leq N \leq 8 $ - $ 1 \leq S_i \leq 2718 $ - $ 1 \leq C_i \leq X \leq 5000 $ - $ 1 \leq P_i \leq 100 $ - All input values are integers.