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?
## Input
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.
## Output
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 .
[samples]
## Note
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.
你正在尝试在你最喜欢的电子游戏中创造纪录。该游戏包含 #cf_span[N] 个关卡，必须按顺序依次完成才能通关。你通常会尽可能快地完成每个关卡，但有时也会较慢地完成。具体来说，你完成第 #cf_span[i] 个关卡的时间要么是 #cf_span[Fi] 秒，要么是 #cf_span[Si] 秒，其中 #cf_span[Fi < Si]，且有 #cf_span[Pi]% 的概率以 #cf_span[Fi] 秒完成。完成一个关卡后，你可以选择继续游戏并进入下一关，或者重置游戏并从第一关重新开始。这两个决策和操作都是瞬时的。
你的目标是在总共不超过 #cf_span[R] 秒的时间内按顺序完成所有关卡。你希望最小化达成该目标前的期望游戏时间。如果你采用最优的继续或重置策略，你预计总共会花费多少时间？
输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[R]，分别表示关卡数量和你希望完成游戏的总秒数上限。接下来有 #cf_span[N] 行，第 #cf_span[i] 行包含三个整数 #cf_span[Fi, Si, Pi] #cf_span[(1 ≤ Fi < Si ≤ 100, 80 ≤ Pi ≤ 99)]，分别表示第 #cf_span[i] 个关卡的快速完成时间、慢速完成时间，以及以快速时间完成该关卡的概率（以百分比表示）。
请输出总期望时间。你的答案必须在绝对误差或相对误差不超过 #cf_span[10 - 9] 的范围内正确。
形式化地，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，你的答案被认为是正确的，当且仅当 。
在第一个示例中，你无需重置。有 #cf_span[81%] 的概率在 #cf_span[2] 秒内完成关卡，有 #cf_span[19%] 的概率需要 #cf_span[8] 秒，两者均未超过目标时间。期望时间为 #cf_span[0.81·2 + 0.19·8 = 3.14]。
在第二个示例中，如果你第一关完成得慢，则应重置。平均而言，你将在第一次快速完成前经历 #cf_span[0.25] 次慢速尝试。之后，无论第二关是快是慢都无关紧要。期望时间为 #cf_span[0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4]。
## Input
输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[R]，分别表示关卡数量和你希望完成游戏的总秒数上限。接下来有 #cf_span[N] 行，第 #cf_span[i] 行包含三个整数 #cf_span[Fi, Si, Pi] #cf_span[(1 ≤ Fi < Si ≤ 100, 80 ≤ Pi ≤ 99)]，分别表示第 #cf_span[i] 个关卡的快速完成时间、慢速完成时间，以及以快速时间完成该关卡的概率（以百分比表示）。
## Output
请输出总期望时间。你的答案必须在绝对误差或相对误差不超过 #cf_span[10 - 9] 的范围内正确。形式化地，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，你的答案被认为是正确的，当且仅当 。
[samples]
## Note
在第一个示例中，你无需重置。有 #cf_span[81%] 的概率在 #cf_span[2] 秒内完成关卡，有 #cf_span[19%] 的概率需要 #cf_span[8] 秒，两者均未超过目标时间。期望时间为 #cf_span[0.81·2 + 0.19·8 = 3.14]。在第二个示例中，如果你第一关完成得慢，则应重置。平均而言，你将在第一次快速完成前经历 #cf_span[0.25] 次慢速尝试。之后，无论第二关是快是慢都无关紧要。期望时间为 #cf_span[0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4]。
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of levels, and $ R \in \mathbb{Z}^+ $ the maximum allowed total time.
For each level $ i \in \{1, \dots, N\} $:
- $ F_i \in \mathbb{Z}^+ $: fast completion time.
- $ S_i \in \mathbb{Z}^+ $: slow completion time, with $ F_i < S_i $.
- $ P_i \in [80, 99] \cap \mathbb{Z} $: probability (as percentage) of completing level $ i $ in $ F_i $ seconds; thus, $ p_i = \frac{P_i}{100} $ is the probability of fast completion, and $ 1 - p_i $ is the probability of slow completion.
**State Space**
Let $ E(i, t) $ denote the minimum expected total time to complete all levels from level $ i $ to $ N $, given that $ t $ seconds have already been spent, and optimal reset decisions are made.
**Constraints**
1. $ 1 \leq N \leq 100 $, $ 1 \leq R \leq 10000 $.
2. $ 1 \leq F_i < S_i \leq 100 $, $ 0.80 \leq p_i \leq 0.99 $.
3. Total time must not exceed $ R $: if $ t + \text{time for level } i > R $, reset is forced.
**Objective**
Compute $ E(1, 0) $, the minimal expected time to complete all $ N $ levels sequentially, starting from level 1 with 0 elapsed time, under optimal reset strategy.
**Recurrence**
For $ i = N, N-1, \dots, 1 $, and $ t = 0, 1, \dots, R $:
$$
E(i, t) = \min \left\{
\begin{array}{l}
p_i \cdot \left( F_i + E(i+1, t + F_i) \right) + (1 - p_i) \cdot \left( S_i + E(i+1, t + S_i) \right), \\
\quad \text{if } t + F_i \leq R \text{ and } t + S_i \leq R \\
\\
p_i \cdot \left( F_i + E(1, 0) \right) + (1 - p_i) \cdot \left( S_i + E(1, 0) \right), \\
\quad \text{if } t + F_i > R \text{ or } t + S_i > R \text{ (reset after this level)}
\end{array}
\right.
$$
With base case:
$$
E(N+1, t) = 0 \quad \forall t \leq R
$$
And $ E(i, t) = \infty $ if $ t > R $.
**Output**
$ E(1, 0) $