Airport Walkways (Small)

Time limit5sMemory limit512 MB

Summary

Spend up to t seconds running, choosing walkway and plain sections, to minimize travel time over a corridor of length X.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

You are in an airport, standing at point 0. A corridor of length $X$ leads to the gate, and your plane is about to leave. The corridor holds moving walkways, and walkway $i$ moves at speed $w_i$ . When you walk or run on one of them, you move at speed (your own speed $+\ w_i$ ). The walkways never change position; they only add to your speed. The walkways do not overlap: at any point of the corridor there is at most one walkway, but one walkway can begin exactly where another one ends.

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

If you choose when to walk and when to run so that you arrive as early as possible, how long does the trip to the gate take?

Input

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$ , separated by spaces: the length of the corridor in metres, your walking speed in metres per second, your running speed in metres per second, the largest total time in seconds that you may run, and the number of walkways.

Each of the next $N$ lines contains three integers $B_i$ , $E_i$ and $w_i$ : the point where the walkway begins, the point where it ends (both in metres from the start), and the speed of the walkway in metres per second. The walkways are given in increasing order of their starting point.

Limits

$1 \le T \le 40$
$1 \le X \le 100$
$1 \le S < R \le 100$
$1 \le t \le 100$
$1 \le N \le 20$
$0 \le B_i < E_i \le X$
$E_i \le B_{i+1}$
$1 \le w_i \le 100$

Output

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 time in seconds needed to reach point $X$ when you walk and run optimally.

Print $y$ rounded to six digits after the decimal point, always with exactly six digits. In the test data the exact answer is at least $10^{-8}$ away from a rounding boundary, so double precision arithmetic is enough.

Note

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

Examples1

Example 1

Input

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

Expected output

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