공항 무빙워크

공항의 0 지점에 서 있다. 길이가 X인 복도가 비행기가 곧 출발할 탑승구까지 이어져 있다. 복도에는 각각 일정한 속도 $w_{i}$로 움직이는 무빙워크가 있다. 그 위에서 걷거나 달리면 (자신의 속도 + $w_{i}$)의 속도로 이동한다. 무빙워크 자체의 위치는 바뀌지 않으며, 단지 더 빠르게 이동하게 해 준다. 무빙워크는 서로 겹치지 않는다. 복도의 어느 지점에든 무빙워크는 최대 하나만 있지만, 한 무빙워크가 끝나는 지점에서 다른 무빙워크가 시작될 수 있다.

평소 걷는 속도는 S이다. 하지만 비행기를 놓칠까 걱정되어 조금 달릴 수 있으며, 총 최대 t초 동안 속도 R로 달릴 수 있다. t초 동안 연속해서 달릴 필요는 없다. 이 t초를 임의의 개수의 구간으로 나누어 사용할 수도 있고, 일부를 사용하지 않아도 된다.

가능한 한 빨리 도착하도록 걸을 때와 달릴 때를 선택한다면 탑승구에 도착하는 데 얼마나 걸리는가?

제한

1 ≤ T ≤ 40. 1 ≤ S < R ≤ 100. 1 ≤ $w_{i}$ ≤ 100. 0 ≤ $B_{i}$ < $E_{i}$ ≤ X. $E_{i}$ ≤ $B_{i+1}$. 메모리 제한: 1GB.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ t ≤ 100. 1 ≤ X ≤ 100. 1 ≤ N ≤ 20. 시간 제한: 30초.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ t ≤ $10^{6}$. 1 ≤ X ≤ $10^{6}$. 1 ≤ N ≤ 1000. 시간 제한: 60초.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다섯 정수를 포함하는 한 줄로 시작한다. X는 복도의 길이(미터), S는 걷는 속도(초당 미터), R은 달리는 속도(초당 미터), t는 달릴 수 있는 최대 시간(초), N은 무빙워크의 수이다.

이어지는 N개의 각 줄에는 세 정수 $B_{i}$, $E_{i}$, $w_{i}$가 주어진다. 이는 무빙워크의 시작점과 끝점(출발점으로부터의 거리, 미터), 그리고 무빙워크의 속도(초당 미터)이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 걷기와 달리기를 최적으로 사용하여 X 지점에 도달하는 데 필요한 시간(초)이다. 상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 인정된다.

첫 번째 테스트 케이스의 최선의 방법은 즉시 달리기 시작하여 일 초 동안 달리는 것이다.