You're in an airport, standing at point . A corridor of length leads to the gate, where your plane is about to leave. There are moving walkways in the corridor, each moving with some speed . When you walk or run on one of those, you move with speed (your speed + ). 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 . You are worried that you might not catch your plane, though, so you can run a bit - you can run with speed for at most seconds in total. You do not have to run for consecutive seconds: you can split these 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, . test cases follow. Each test case begins with a line containing five integers: (the length of the corridor, in meters), (your walking speed, in meters per second), (your running speed, in meters per second), (the maximum time you can run, in seconds) and (the number of walkways).
Each of the next lines contains three integers: , and - 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 #: ", where is the case number (starting from ) and is the time (in seconds) you need to reach point if you walk and run optimally. Answers with relative or absolute error of at most will be accepted.
