공항 무빙워크 (큰 입력)

공항 안 출발점 0에 서 있다. 게이트까지 이어지는 복도의 길이는 $X$이고, 복도에는 무빙워크가 놓여 있다. $i$번 무빙워크는 게이트 쪽으로 속력 $w_i$로 움직인다. 그 위에서 걷거나 뛰면 이동 속력은 자신의 속력에 $w_i$를 더한 값이 된다. 무빙워크 자체는 자리를 옮기지 않고 사람을 더 빠르게 옮겨 줄 뿐이다. 무빙워크끼리 겹치지 않는다. 복도의 한 지점을 덮는 무빙워크는 많아야 하나지만, 한 무빙워크가 끝나는 지점에서 다른 무빙워크가 시작할 수는 있다.

평소 걷는 속력은 $S$다. 비행기를 놓칠까 걱정되어 조금 뛸 수도 있다. 속력 $R$로 뛰며, 뛰는 시간은 모두 합쳐 최대 $t$초다. $t$초를 연달아 쓸 필요는 없다. 원하는 만큼 여러 구간으로 나눠 써도 되고, 일부를 남겨도 된다.

가장 빨리 게이트에 닿도록 걷는 구간과 뛰는 구간을 정했을 때, 지점 $X$까지 걸리는 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스의 첫 줄에는 정수 다섯 개 $X$, $S$, $R$, $t$, $N$이 주어진다. $X$는 복도의 길이(미터), $S$는 걷는 속력(초당 미터), $R$은 뛰는 속력(초당 미터), $t$는 뛸 수 있는 시간의 총합(초), $N$은 무빙워크의 개수다.

다음 $N$개의 줄에는 각각 정수 세 개 $B_i$, $E_i$, $w_i$가 주어진다. $B_i$와 $E_i$는 출발점에서 잰 무빙워크의 시작 위치와 끝 위치(미터)이고, $w_i$는 무빙워크의 속력(초당 미터)이다. 무빙워크는 시작 위치가 커지는 순서로 주어진다.

제한

• $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$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 지점 $X$에 닿는 데 걸리는 최소 시간(초)이다.

$y$는 소수점 아래 여섯째 자리에서 반올림해 소수점 아래 자리를 정확히 여섯 개 적는다. 값이 작아도 4.000000처럼 여섯 자리를 모두 채운다. 테스트 데이터의 모든 답은 반올림 경계에서 충분히 떨어져 있으므로, 반올림 방향이 갈리는 경우는 없다.

첫 번째 예제에서는 출발하자마자 1초 동안 뛰는 것이 최선이다.