보물 지도

무인도에 상륙한 지점에서 보물이 묻힐 X 지점까지 가는 여러 단계를 적어 둔 해적의 지도를 손에 넣었습니다. 각 단계는 나침반 방위와 걸음 수로 이루어집니다.

모아 둔 돈의 대부분을 들여 배를 빌려 섬에 도착한 뒤, 휴대용 GPS 수신기의 도움을 받아 지도의 지시를 그대로 따라 걸었습니다. 그런데 보물이 없습니다! 집으로 돌아와서야, 해적들은 GPS를 몰랐고 자기 나침반으로 지도를 만들었다는 사실을 알게 됩니다. 그들은 자신들의 나침반이 진북이 아니라 자북을 가리킨다는 것을 몰랐습니다. 자북과 진북 사이의 각도는 지구 위 위치에 따라 달라지는데, 이 무인도에서는 자북이 진북으로부터 $d$도 떨어져 있음을 알아냈습니다.

당신은 모든 방위를 (GPS의) 진북 기준으로 걸었지만 해적들은 모든 방위를 자북 기준으로 측정했기 때문에, 당신의 경로는 해적의 경로에서 회전되어 결국 X에 도달하지 못했습니다. 보물 X를 해적의 지시가 실제로 가리키는 지점(같은 단계들을 따르되 각 방위를 자북 기준으로 해석한 지점)이라고 할 때, 지도를 따라 걷는 동안 어느 한 순간이라도 X에 가장 가까웠던 거리는 얼마입니까?

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 지도의 단계 수 $n$ ($n \le 1000$)이 적힌 줄로 시작합니다. 이어지는 $n$개의 줄에는 각각 32개의 이름 붙은 나침반 방위(힌트 참고) 중 하나와 걸음 수가 적혀 있습니다. 그 다음 한 줄에는 자북과 진북 사이의 각도 $d$가 도 단위로 주어집니다. 양수는 자북이 진북의 동쪽에, 음수는 서쪽에 있음을 뜻하며 $|d| \le 90$입니다. 마지막 테스트 케이스 뒤에는 $0$ 하나만 있는 줄(단계 수가 0)이 와서 입력이 끝납니다.

각 테스트 케이스마다, 지도를 따라 걷는 동안 어느 순간에든 보물과 당신 사이를 갈라놓았던 최소 거리를 걸음 수 단위로, 소수점 아래 둘째 자리까지 반올림하여 한 줄에 하나의 수로 출력하세요.

나침반 방위의 이름은 N, E, S, W, b 글자들의 조합입니다(여기서 “b”는 “by”를 뜻합니다). 예를 들어 NEbE는 북동미동(north-east by east)을 뜻합니다. 32개의 방위는 나침반 둘레에 $11.25$도 간격으로 고르게 배치되어 있습니다. 북(N)에서 시작하여 시계 방향으로 나열하면 다음과 같습니다:

N NbE NNE NEbN NE NEbE ENE EbN E EbS ESE SEbE SE SEbS SSE SbE S SbW SSW SWbS SW SWbW WSW WbS W WbN WNW NWbW NW NWbN NNW NbW