동굴 탐험

여러 탐험가가 동굴 입구에 있다. 목표는 모든 탐험가가 동굴을 통과해 출구 쪽에 모이는 것이다.

동굴 안에서는 지도가 반드시 필요하지만, 지도는 하나뿐이다. 따라서 한 번에 이동하는 그룹은 지도를 가지고 있어야 하며, 다음 이동도 지도가 있는 쪽에서 시작한다. 지도를 가져오기 위해 이미 출구 쪽에 있는 탐험가가 입구 쪽으로 돌아올 수도 있다.

탐험가들은 이동 중 낡은 다리를 건너야 한다. 한 그룹에 속한 모든 탐험가는 동시에 다리를 건너며, 그 그룹의 총무게가 다리가 견딜 수 있는 한계 B를 넘으면 안 된다.

탐험가는 혼자 이동할 수 있다. 두 명 이상이 함께 이동하려면, 그룹의 각 탐험가가 같은 그룹 안의 다른 탐험가 중 적어도 한 명을 신뢰해야 한다.

탐험가마다 걷는 시간이 다르다. 한 그룹이 함께 이동할 때 걸리는 시간은 그 그룹에서 가장 느린 탐험가의 시간이다.

모든 탐험가를 출구 쪽으로 옮기는 데 필요한 최소 시간을 구하라.

첫째 줄에 탐험가의 수 N이 주어진다. N은 13 이하의 자연수이다.

다음 N개의 줄에는 각 탐험가의 무게와 걷는 시간이 주어진다. 두 값은 모두 1,000 이하의 자연수이다.

그다음 N개의 줄에는 탐험가 사이의 신뢰 관계가 주어진다. i번째 줄의 j번째 문자가 Y이면 탐험가 i가 탐험가 j를 신뢰한다는 뜻이고, N이면 신뢰하지 않는다는 뜻이다. i번째 줄의 i번째 문자는 항상 Y이며, 신뢰 관계는 대칭일 필요가 없다.

마지막 줄에는 다리가 견딜 수 있는 무게 한계 B가 주어진다. B는 5,000 이하의 자연수이다.

모든 탐험가가 출구 쪽으로 이동하는 데 걸리는 최소 시간을 출력한다. 모든 탐험가를 이동시킬 수 없다면 -1을 출력한다.

첫 번째 공개 테스트에서는 탐험가 1과 3이 함께 출구 쪽으로 이동하고, 탐험가 1이 혼자 입구 쪽으로 돌아온 뒤, 탐험가 1과 2가 함께 출구 쪽으로 이동하면 총 시간이 4 + 2 + 3 = 9가 된다.