题目描述

You're in an airport, standing at point $0$. A corridor of length $X$ leads to the gate, where your plane is about to leave. There are moving walkways in the corridor, each moving with some speed $w_i$. When you walk or run on one of those, you move with speed (your speed + $w_i$). The walkways do not change their position; they just make you move faster. The walkways do not overlap: at any given point of the corridor there is at most one walkway, but one walkway can begin at the point where another ends.

Your normal walking speed is $S$. You are worried that you might not catch your plane, though, so you can run a bit - you can run with speed $R$ for at most $t$ seconds in total. You do not have to run for $t$ consecutive seconds: you can split these $t$ seconds into any number of intervals, or even not use some part of them.

How long does it take you to get to the gate, assuming you choose when to walk and when to run in order to reach it as soon as possible?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing five integers: $X$ (the length of the corridor, in meters), $S$ (your walking speed, in meters per second), $R$ (your running speed, in meters per second), $t$ (the maximum time you can run, in seconds) and $N$ (the number of walkways).

Each of the next $N$ lines contains three integers: $B_i$, $E_i$ and $w_i$ - the beginning and end of the walkway (in meters from your starting point) and the speed of the walkway (in meters per second).

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the case number (starting from $1$) and $y$ is the time (in seconds) you need to reach point $X$ if you walk and run optimally. Answers with relative or absolute error of at most $10^{-6}$ will be accepted.

3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

提示

Sample Explanation

The best solution in the first case is to start running immediately and run for one second.

Limits

• $1 \leq T \leq 40$.
• $1 \leq S < R \leq 100$.
• $1 \leq w_i \leq 100$.
• $0 \leq B_i < E_i \leq X$.
• $E_i \leq B_{i+1}$.

Small dataset (8 Pts, Test set 1 - Visible)

• $1 \leq t \leq 100$.
• $1 \leq X \leq 100$.
• $1 \leq N \leq 20$.
• Time limit: 30 3 seconds.

Large dataset (10 Pts, Test set 2 - Hidden)

• $1 \leq t \leq 10^6$.
• $1 \leq X \leq 10^6$.
• $1 \leq N \leq 1000$.
• Time limit: 60 6 seconds.