CF865C.Gotta Go Fast

You're trying to set the record on your favorite video game. The game consists of N levels, which must be completed sequentially in order to beat the game. You usually complete each level as fast as possible, but sometimes finish a level slower. Specifically, you will complete the i-th level in either F__i seconds or S__i seconds, where F__i < S__i, and there's a P__i percent chance of completing it in F__i seconds. After completing a level, you may decide to either continue the game and play the next level, or reset the game and start again from the first level. Both the decision and the action are instant.

Your goal is to complete all the levels sequentially in at most R total seconds. You want to minimize the expected amount of time playing before achieving that goal. If you continue and reset optimally, how much total time can you expect to spend playing?

你正试图刷新自己最喜爱的电子游戏的纪录。该游戏共有 $N$ 个关卡，必须按顺序依次完成所有关卡才能通关。你通常会以尽可能快的速度完成每个关卡，但有时也会较慢地完成某一关。具体而言，你完成第 $i$ 关所需的时间为 $F_i$ 秒或 $S_i$ 秒（其中 $F_i < S_i$），且以 $F_i$ 秒完成的概率为 $P_i$ 百分比。每完成一关后，你可以立即决定：继续游戏并进入下一关，或者重置游戏并从第一关重新开始。这两项操作（决策与执行）均不耗时。

你的目标是在总计不超过 $R$ 秒的时间内，按顺序完成全部关卡。你希望最小化达成该目标前的期望总游戏时间。若你以最优策略决定继续或重置，那么你预期总共需要花费多少时间进行游戏？

The first line of input contains integers N and R , the number of levels and number of seconds you want to complete the game in, respectively. N lines follow. The _i_th such line contains integers F__i, S__i, P__i (1 ≤ F__i < S__i ≤ 100, 80 ≤ P__i ≤ 99), the fast time for level i, the slow time for level i, and the probability (as a percentage) of completing level i with the fast time.

输入的第一行包含两个整数 $N$ 和 $R$ ，分别表示关卡数量以及你希望完成游戏所用的秒数。接下来有 $N$ 行。其中第 $i$ 行包含三个整数 $F_i$、$S_i$、$P_i$（满足 $1 \leq F_i < S_i \leq 100$，且 $80 \leq P_i \leq 99$），分别表示第 $i$ 关的快速通关时间、慢速通关时间，以及以快速时间完成第 $i$ 关的概率（以百分比形式给出）。

Print the total expected time. Your answer must be correct within an absolute or relative error of 10 - 9.

Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if .

输出总期望时间。你的答案必须在绝对或相对误差 $10^{-9}$ 范围内正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。若满足 ，则你的答案被视为正确。

In the first example, you never need to reset. There's an 81% chance of completing the level in 2 seconds and a 19% chance of needing 8 seconds, both of which are within the goal time. The expected time is 0.81·2 + 0.19·8 = 3.14.

In the second example, you should reset after the first level if you complete it slowly. On average it will take 0.25 slow attempts before your first fast attempt. Then it doesn't matter whether you complete the second level fast or slow. The expected time is 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4.

在第一个例子中，你永远不需要重置。有 $81\%$ 的概率在 $2$ 秒内完成该关卡，另有 $19\%$ 的概率需要 $8$ 秒，这两种情况均未超过目标时间。期望时间为 $0.81 \cdot 2 + 0.19 \cdot 8 = 3.14$。

在第二个例子中，若你在第一关耗时较长，则应在第一关结束后立即重置。平均而言，在首次快速完成之前，你会进行 $0.25$ 次慢速尝试。此后，第二关是快速还是慢速完成均无影响。期望时间为 $0.25 \cdot 30 + 20 + 0.85 \cdot 3 + 0.15 \cdot 9 = 31.4$。