Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Gotta Go Fast

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou'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 .

Examples

Input

1 8

2 8 81

Output

3.14

Input

2 30

20 30 80

3 9 85

Output

31.4

Input

4 319

63 79 89

79 97 91

75 87 88

75 90 83

Output

314.159265358

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 00:07:08 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|