#1368 경찰서 건설

58  1 s   128 MB  

Description

도시에 N 개의 지점이 있다. 이 지점들은 다른 지점들과 일방통행 도로로 연결될 수 있다.

시장인 당신은 이 지점들 중 일부에 경찰서를 건설하고자 한다. 각 지점마다 경찰서를 건설하는 비용이 다르며, i번째 지점에 경찰서를 건설하는 비용은Ci 이다.

경찰서의 관할 지역은, 경찰서가 위치한 지점으로부터 출발해 사건을 처리하고 돌아올 수 있는 모든 지점으로 정의된다. 모든 지점이 적어도 하나 이상의 경찰서의 관할 지역에 포함되도록 경찰서를 짓고자 할 때, 필요한 최소 비용은 얼마인가?

Input

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

각 테스트 케이스의 첫 행에는 지점의 수 N (1 <= N <= 50) 이 주어진다.

다음 행에는 각 지점에 경찰서를 건설할 때의 비용인 N 개의 정수 Ci 가 공백으로 구분되어 주어진다. 이 값들은 1 이상 10^6 이하이다.

다음 N 개의 행에 걸쳐서 각 지점들 사이의 연관 관계를 표현하는 길이가 N인 문자열이 각각 주어진다. i행 j열의 문자가 'Y'인 경우 지점 i에서 지점 j로 가는 일방통행 도로가 있음을 의미한다. i행 i열의 문자는 언제나 'N'이다. 

Output

각 테스트 케이스에 대해 최소 비용을 한 행에 하나씩 순서대로 출력한다.

Sample Input

Sample Output

1
5
1 2 3 4 5
NNNYY
YNNNN
NNNYN
NNYNN
NYNNN
4