풍선 점 잇기

점 잇기 놀이를 해 본 적이 있는가? 그림에 소질이 없는 사람도 점 잇기로는 근사한 그림을 그릴 수 있다. 종이에 점이 $n$개 있고 각 점에는 $1$부터 $n$까지의 정수가 하나씩 붙어 있다. 여기에 선분 $n-1$개를 긋는다. $1$번과 $2$번을 잇고, $2$번과 $3$번을 잇고, $3$번과 $4$번을 잇는 식으로 끝까지 이어 나가면 그림이 완성된다. 다음은 점을 잇기 전과 후의 예다.

이번에는 풍선 표면에 점 잇기 그림을 그리려고 한다. 풍선은 완전한 구라고 가정한다. 처음에 풍선의 반지름은 1센티미터다. 표면에 점 $n$개를 그려 두고 각각 $1$번부터 $n$번까지 번호를 매겼다. 풍선을 불수록 점 사이의 간격은 점점 벌어진다. 목표는 그림을 최대한 크게 만드는 것, 즉 선 $n-1$개의 길이 합을 최대로 만드는 것이다.

그림이 흐려지지 않도록 풍선을 먼저 끝까지 불고, 그 뒤에야 선 $n-1$개를 그린다. 풍선은 1분에 $v$세제곱센티미터씩 부풀릴 수 있고, 선은 1분에 $d$센티미터씩 그릴 수 있다. $i$번 점에서 $i+1$번 점으로 선을 그을 때는 풍선 표면을 따라 최단 경로로 긋는다. 최단 경로가 여러 개인 경우도 있지만, 이 문제는 길이만 따지므로 어느 쪽을 그리든 결과는 같다.

쓸 수 있는 시간은 모두 $T$분이다. 풍선을 부는 시간과 선을 그리는 시간을 합쳐 $T$분을 넘길 수 없다. 그리기를 마쳤을 때 선 $n-1$개는 모두 완성되어 있어야 한다. 그릴 수 있는 길이 합의 최댓값을 구하여라.

첫째 줄에 정수 $n$, $T$, $v$, $d$가 주어진다. $n$ ($2 \le n \le 1000$)은 점의 개수, $T$ ($1 \le T \le 10^6$)는 풍선을 불고 선 $n-1$개를 그리는 데 쓸 수 있는 전체 시간(분), $v$ ($1 \le v \le 1000$)는 1분에 부풀릴 수 있는 부피(세제곱센티미터), $d$ ($1 \le d \le 1000$)는 1분에 그을 수 있는 선의 길이(센티미터)다.

다음 $n$개 줄에는 $1$번부터 $n$번까지 점의 위치가 순서대로 주어진다. 풍선의 중심은 원점이다. 각 줄에는 실수 $x$와 $y$, 정수 $s$ ($s \in \{-1, 1\}$)가 주어진다. 점의 좌표는 $(x, y, z)$이고 $z = s\sqrt{1 - x^2 - y^2}$이다. $0 \le x^2 + y^2 \le 1$이 보장되며 $x$와 $y$의 단위는 센티미터다. $x$와 $y$는 소수점 아래 최대 6자리까지 주어진다.

선끼리 서로 만나거나 완전히 겹칠 수 있다. 겹치는 부분은 겹친 횟수만큼 거듭 세어서 더한다. 반지름이 1인 풍선 위에 이 그림을 $T$분 안에 그릴 수 있다는 것은 보장된다.

그릴 수 있는 그림의 길이 합의 최댓값을 센티미터 단위로 출력한다. 소수점 아래 일곱째 자리에서 반올림하여 소수점 아래 여섯 자리를 정확히 출력한다.

$x^2 + y^2 = 1$인 경우를 조심해야 한다. $1 - x^2 - y^2$을 계산하면 부동소수점 오차 때문에 $-0.0000000001$처럼 아주 작은 음수가 나올 수 있고, 그러면 제곱근을 구하는 데 실패한다. 같은 이유로 두 점이 이루는 각의 코사인값도 $[-1, 1]$을 살짝 벗어날 수 있다. 아크코사인을 취하기 전에 값을 이 범위로 잘라 주면 안전하다.