시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 112 29 21 23.333%

문제

대구과학고등학교 장홍준 교장 선생님은 부임 10주년 기념으로 세미나를 열려고 한다. 교장 선생님은 세미나의 원활한 진행을 위해 전교생을 두 개의 조로 나누려고 한다.

장홍준 교장은 항상 학생들간의 소통이 중요하다고 말해왔다. 따라서, 서로 싫어하는 학생의 쌍을 이미 알고 있고, 서로 싫어하는 학생들 끼리는 같은 조에 배정하지 않으려고 한다. 또, 같은 학년은 같은 조에 배정되어야 한다.

신기하게도 같은 학년 끼리는 서로 싫어하지 않고, 선후배 관계인 두 학생이 서로 싫어하는 경우만 있다.

장홍준 교장은 여러 번 시도를 한 끝에 위의 조건을 만족하면서 전교생 모두가 세미나에 참석할 수 있게 조를 나누는 것이 불가능하다는 것을 깨달았다. 장홍준 교장은 위의 조건을 만족하면서 자신의 세미나에 최대한 많은 학생이 오기를 바란다.

세미나에 참석할 수 있는 학생 수의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 N이 주어진다. (1 ≤ N ≤ 50)

다음 줄에 학생의 학년 정보가 공백 없이 주어진다. i번째로 주어지는 수는 i번 학생의 학년 Gi이다. (1 ≤ Gi ≤ 3, 1 ≤ i ≤ N)

다음 N개 줄에는 학생들의 관계가 공백없이 주어진다. i번 학생과 j번 학생이 서로 싫어하는 i+2번째 줄의 j번째 칸과 j+2번째 줄의 i번째 칸은 'Y'이고, 그렇지 않은 경우에는 'N'이다.

출력

세미나를 들을 수 있는 최대 학생 수를 출력한다.

예제 입력

3
123
NYY
YNY
YYN

예제 출력

2

힌트

출처