题目描述

你要沿直线从位置 $0$ 到达位置 $x$。普通路面步行速度为 $s$，跑步速度为 $r$，累计跑步时间不超过 $t$。可以在任意位置切换走路和跑步。有 $n$ 段互不重叠的传送带，第 $i$ 段为 $[B_i,E_i]$，传送速度为 $w_i$，站在上面时步行、跑步速度都增加 $w_i$。求最短到达时间。

输入格式

第一行测试组数 $test$。每组第一行五个整数 $x,s,r,t,n$。接下来 $n$ 行，每行三个整数 $B_i,E_i,w_i$，按起点递增。

输出格式

每组输出 Case #编号: 答案，编号从1开始，答案保留小数点后9位。

样例

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.000000000
Case #2: 5.500000000
Case #3: 3.538095238

数据范围

$1\le test\le4$，$1\le s<r\le100$，$1\le w_i\le100$，$0\le B_i<E_i\le x$，$E_i\le B_{i+1}$，$1\le t,x\le10^6$，$1\le n\le1000$。