발전소

은진이는 발전소에서 근무한다. 은진이가 잠깐 자는 사이 일부 발전소가 고장 났고, 상사가 사무실에 도착하기 전까지 발전소를 복구해야 한다.

고장 나지 않은 발전소 하나를 이용하면 고장 난 발전소 하나를 다시 시작할 수 있다. 이때 드는 비용은 어떤 발전소로 어떤 발전소를 다시 시작하는지에 따라 다르다.

적어도 P개의 발전소가 정상 작동하도록 만들기 위해 필요한 최소 비용을 구하라.

첫째 줄에 발전소의 개수 N이 주어진다. N은 16 이하의 자연수이다.

다음 N개 줄에는 비용 행렬이 주어진다. i번째 줄의 j번째 값은 i번 발전소를 이용해 j번 발전소를 다시 시작할 때 드는 비용이다.

그다음 줄에는 각 발전소의 현재 상태가 길이 N의 문자열로 주어진다. 켜져 있으면 Y, 꺼져 있으면 N이다.

마지막 줄에 목표 개수 P가 주어진다. 모든 비용은 36 이하의 음이 아닌 정수이고, P는 0 이상 N 이하의 정수이다.

적어도 P개의 발전소가 작동하도록 만드는 최소 비용을 출력한다. 불가능하면 -1을 출력한다.