경찰

2100년, 민식이는 남극에 살고 있다. 남극에는 N개의 마을이 있고, 일부 마을 사이에는 좁은 일방통행 도로가 있다.

각 마을에 경찰서를 세우는 비용이 주어진다. 모든 마을에 경찰서를 세울 필요는 없지만, 모든 마을은 적어도 하나의 경찰서가 있는 마을에서 도로를 따라 도달할 수 있어야 한다.

대통령은 이 조건을 만족하면서 선택한 경찰서 설치 비용의 평균을 최대한 낮추려고 한다.

마을별 설치 비용과 도로 정보가 주어질 때, 가능한 최소 평균 비용을 구하시오.

첫째 줄에 마을의 개수 N이 주어진다. N은 50 이하의 자연수이다.

둘째 줄에는 0번 마을부터 N-1번 마을까지 경찰서를 설치하는 비용이 주어진다. 각 비용은 1000 이하의 자연수이다.

셋째 줄부터 N개의 줄에는 도로 정보가 인접행렬 형식으로 주어진다. 마을 i에 해당하는 줄의 j번째 문자가 Y이면 i에서 j로 가는 도로가 있고, N이면 도로가 없다. i에서 i로 가는 도로는 없다.

첫째 줄에 정답을 출력한다. 절대 오차 또는 상대 오차가 10^-9 이하이면 정답으로 인정된다.