출근 전쟁 (Small)

문제

영수는 다음 주에 첫 출근을 앞두고 있다. 서울의 대중교통은 잘 갖춰져 있지만, 사정이 생겨 모든 교통수단이 검문을 받게 되었다. 첫 출근에 지각하지 않으려고 영수는 회사로 가는 길목의 교통편 시간표와 예상 지연 시간을 미리 모아 두었다. 영수가 회사에 도착하는 시각의 기댓값을 구하라.

교통 수단 하나는 다음과 같이 움직인다.

출발 길목에서 매시 $S$ 분에 출발한다. 즉 시각 $S$ , $S+60$ , $S+120$ , ... 에 출발한다. 영수가 시각 $t$ 에 출발 길목에 있으면 $t$ 이상인 가장 이른 출발 시각의 차를 탄다. $t$ 가 출발 시각과 같으면 그 차를 탄다.
도착 길목까지 가는 데 $R$ 분이 걸린다.
이동 도중 경찰의 검문을 받는다. 검문 자체에는 시간이 걸리지 않지만 $P$ 퍼센트의 확률로 문제가 있어서 $D$ 분 동안 지연된다. $D$ 분이 지나면 다시 검문을 받고, 이때도 같은 확률로 또 지연된다. 검문은 통과할 때까지 무한히 반복된다. 검문에서 $k$ 번 문제가 생기면 이동에 걸리는 시간은 $R + D \times k$ 분이다.
차에 탄 뒤에는 도착 길목에 닿기 전에 내릴 수 없다.

$P = 100$ 인 교통 수단은 검문을 절대 통과하지 못하므로 도착 길목에 닿지 못한다.

영수가 집에서 출발하는 시각은 $0$ 이고, 어느 길목에서든지 도착 시각의 기댓값을 최소화하는 교통 수단을 선택한다.

입력

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

각 테스트 케이스의 첫 줄에는 정수 $N$ , $M$ , $H$ , $O$ 가 공백으로 구분되어 주어진다. $N$ 은 길목의 수, $M$ 은 교통 수단의 수, $H$ 는 집이 있는 길목 번호, $O$ 는 회사가 있는 길목 번호이다.

이어지는 $M$ 개의 줄에는 교통 수단마다 정수 여섯 개 $A_i$ , $B_i$ , $S_i$ , $R_i$ , $D_i$ , $P_i$ 가 주어진다. $A_i$ 는 출발 길목 번호, $B_i$ 는 도착 길목 번호, $S_i$ 는 매시 출발하는 분, $R_i$ 는 이동 소요 시간, $D_i$ 는 한 번 지연될 때 늘어나는 시간, $P_i$ 는 검문에서 문제가 생길 확률이다. $P_i$ 는 퍼센트 값이다.

제한

$1 \le T \le 100$
$2 \le N \le 100$
$0 \le M \le N - 1$
$0 \le H, O, A_i, B_i < N$
$0 \le S_i \le 59$
$1 \le R_i \le 100$
$1 \le D_i \le 100$
$0 \le P_i \le 100$
모든 $i$ 에 대해 $B_i = A_i + 1$
$i < j$ 인 모든 쌍에 대해 $A_i \ne A_j$ 또는 $B_i \ne B_j$ . 따라서 한 길목에서 출발하는 교통 수단은 많아야 하나다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이다.

영수가 회사에 도착할 수 있으면 $y$ 는 도착 시각의 기댓값을 반올림해 소수점 아래 일곱 자리까지 적은 값이다. 일곱 자리를 모두 적으므로 기댓값이 정확히 정수여도 소수점 아래 $0$ 일곱 개를 붙인다. 도착할 수 없으면 $y$ 자리에 소수점 없이 -1을 출력한다. $H = O$ 이면 기댓값이 $0$ 이므로 0.0000000을 출력한다.