CF865C Gotta Go Fast

你正在尝试在你最喜欢的视频游戏中创造记录。该游戏共有 $N$ 个关卡，必须依次通过才能通关。你通常会以最快速度完成每个关卡，但有时会以较慢速度完成。具体来说，你完成第 $i$ 个关卡的时间要么是 $F_{i}$ 秒，要么是 $S_{i}$ 秒，其中 $F_{i} < S_{i}$，以 $F_{i}$ 秒完成的概率为 $P_{i}\%$。每完成一个关卡后，你可以选择继续进行下一个关卡，或者重置游戏，从第一个关卡重新开始。做出选择和执行操作都是瞬时完成的。 你的目标是在总共不超过 $R$ 秒内依次完成所有关卡。你希望在达到该目标前，所花的期望游戏时间尽可能最小。如果你能最优地选择继续还是重置，问你期望花费的总时间是多少？

输入的第一行包含整数 $N$ 和 $R$，分别表示关卡数和希望完成游戏的最大总用时。 接下来的 $N$ 行，每行包含三个整数 $F_{i}, S_{i}, P_{i}$，分别表示第 $i$ 个关卡的最快用时、最慢用时，以及以最快用时完成的概率（百分比），满足 $1 \leq F_{i} < S_{i} \leq 100,\ 80 \leq P_{i} \leq 99$。

输出期望所花的总时间。你的答案的绝对误差或相对误差需不超过 $10^{-9}$。 形式化地，设你的答案为 $a$，裁判的答案为 $b$，如果 $|a-b|/\max(1,|b|) < 10^{-9}$，则视为正确。

在第一个样例中，你从不需要重置。有 $81\%$ 的概率以 $2$ 秒通过该关卡，$19\%$ 的概率以 $8$ 秒通过，这两种情况都在目标用时内。期望用时为 $0.81 \times 2 + 0.19 \times 8 = 3.14$。 在第二个样例中，如果第一次慢速通过关卡，你应该选择重置。在平均 $0.25$ 次慢通过尝试后，你会首次以最快速度通过关卡。然后，不管第二关是快是慢，都无所谓。期望用时是 $0.25 \times 30 + 20 + 0.85 \times 3 + 0.15 \times 9 = 31.4$。 由 ChatGPT 5 翻译