Airport Walkways (Large)

You are in an airport, standing at point 0. A corridor of length $X$ leads to your gate. The corridor contains moving walkways, and walkway $i$ moves toward the gate at speed $w_i$. While you walk or run on that walkway, your speed is your own speed plus $w_i$. The walkways never change position; they only carry you faster. The walkways do not overlap: at most one walkway covers any point of the corridor, but one walkway may begin exactly where another ends.

Your normal walking speed is $S$. You are worried about missing the plane, so you can also run. You run at speed $R$, for at most $t$ seconds in total. The $t$ seconds do not have to be consecutive. You may split them into any number of intervals, and you may leave part of them unused.

Decide when to walk and when to run so that you reach point $X$ as early as possible, and report that time.

The first line contains the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains five integers $X$, $S$, $R$, $t$ and $N$: the length of the corridor in meters, your walking speed in meters per second, your running speed in meters per second, the total time in seconds you are allowed to run, and the number of walkways.

Each of the next $N$ lines contains three integers $B_i$, $E_i$ and $w_i$: the beginning and the end of the walkway in meters from your starting point, and the speed of the walkway in meters per second. The walkways are given in increasing order of beginning position.

Limits

• $1 \le T \le 40$
• $1 \le S < R \le 100$
• $1 \le w_i \le 100$
• $0 \le B_i < E_i \le X$
• $E_i \le B_{i+1}$
• $1 \le t \le 10^6$
• $1 \le X \le 10^6$
• $1 \le N \le 1000$

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the shortest time in seconds needed to reach point $X$.

Round $y$ at the sixth digit after the decimal point and print exactly six digits after the point, so a small value still prints as 4.000000. Every answer in the test data sits far from a rounding boundary, so the rounding direction is never in doubt.

In the first example case, the best plan is to start running immediately and run for one second.