Problem Description

Giga Street is a straight road running from west to east, with a length of $ L $ meters.

E869120 starts at the west end of Giga Street, riding a car that can travel $ V_S $ meters per minute and has $ D_S $ meters of remaining fuel.

In addition to this car, there are $ N $ other cars on the street. The $ i $-th car is located $ X_i $ meters from the west end, can travel $ V_i $ meters per minute, and has $ D_i $ meters of remaining fuel.

You want to drive from west to east and reach the east end of Giga Street.

He can drive to a spot where a car is parked and switch to that car. The time taken for switching cars is considered to be $ 0 $ minutes.

Can he reach the east end of Giga Street? If it's impossible, report this. If it's possible, report the shortest time (in minutes) required to reach the east end.

Input Format

None

Output Format

If it's impossible to reach the east end of Giga Street, output impossible.
If it's possible, output the shortest time (in minutes) required. This can be in any number of decimal places, but it must be within an absolute or relative error of $ 10^{-5} $ from the correct answer.

Sample Input and Output

Sample Input #1

3 10
1 5
3 5 8
6 10 5
7 2 7

Sample Output #1

4.000000000000000000000

Sample Input #2

3 10
1 5
3 5 8
6 1 5
7 2 7

Sample Output #2

4.400000000000000355271

Sample Input #3

2 10
1 4
3 1 2
6 1 10

Sample Output #3

impossible

Sample Input #4

0 1
99991 1

Sample Output #4

0.000010000900081007291

Sample Input #5

1 100
5 60
50 7 90

Sample Output #5

17.142857142857142349612

Sample Input #6

4 1000
37 426
725 16 612
237 19 458
516 13 509
408 17 400

Sample Output #6

46.861585850556437549130

Notes/Hints

Constraints

• $0 \leq N \leq 2019$
• $1 \leq L \leq 40075017$
• $1 \leq X_1, X_2, \dots, X_N \leq L-1$
• $X_1, X_2, \dots, X_N$ are all distinct
• $1 \leq V_S, V_1, V_2, \dots, V_N \leq 100000$
• $1 \leq D_S, D_1, D_2, \dots, D_N \leq L$
• All inputs are integers

Subtasks

This problem is divided into several sub-tasks. A sub-task is considered solved if all test cases in that sub-task are solved correctly. The score for a submission is the sum of the points for the solved sub-tasks.

1. (9 points) $ N = 0 $
2. (6 points) $ N = 0 $ or $ N = 1 $
3. (22 points) $N \leq 10$
4. (30 points) $ V_S = 1 $ and for all $ i $, $ V_i = 1 $
5. (33 points) No additional constraints

Hint for Subtask 4

This sub-task is a problem of determining whether you can reach the east end. This is because if you can reach it, the shortest time will always be $ L $ minutes since you travel at a speed of $ 1 $ meter per minute everywhere. Those tackling Subtask 4 might find this hint useful.

Sample Explanation 1

The following movement takes $ 4 $ minutes to reach the east end of Giga Street, which is the shortest time:
- First, drive from the west end to $ 3 $ meters using the initial car. This takes $ 3/1 = 3 $ minutes.
- Then, switch to the first car and drive to $ 6 $ meters from the west end. This takes $ 3/5 = 0.6 $ minutes.
- Finally, switch to the second car and drive to the east end ($ 10 $ meters from the west end). This takes $ 4/10 = 0.4 $ minutes.
- The total time is $ 3 + 0.6 + 0.4 = 4 $ minutes.

Sample Explanation 2

The following movement takes $ 4.4 $ minutes to reach the east end of Giga Street, which is the shortest time:
- First, drive from the west end to $ 3 $ meters using the initial car. This takes $ 3/1 = 3 $ minutes.
- Then, switch to the first car and drive to the east end ($ 10 $ meters from the west end). This takes $ 7/5 = 1.4 $ minutes.
- The total time is $ 3 + 1.4 = 4.4 $ minutes.

Sample Explanation 3

In this case, it's impossible to reach the east end of Giga Street. Also, Sample Input/Output 3 satisfies the constraints of Subtask 4 ($ V_S = 1 $, $ V_i = 1 $).

Sample Explanation 4

Note that the answer should be output in the format like 0.00001000090008 instead of 1.00009e-05. Also, Sample Input/Output 4 satisfies the constraints of Subtask 1 ($ N = 0 $).

Sample Explanation 5

In this case, switching at $ 50 $ meters from the west end is optimal. Also, Sample Input/Output 5 satisfies the constraints of Subtask 2 ($ N = 0 $ or $ N = 1 $).

Sample Explanation 6

Since an absolute or relative error within $ 10^{-5} $ is considered correct, outputs like 46.861585 or 46.86159 are also correct.

见题面 Input 部分

见题面 Output 部分