발전소 복구

문제

N개의 발전소가 있으며, 각 발전소는 현재 가동 중이거나 정지 상태이다. 정지된 발전소 i를 가동시키려면 이미 가동 중인 발전소 j가 필요하며, 이때 발생하는 비용은 $P[i][j]$이다.

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

입력

첫째 줄에 발전소의 수 N이 주어진다. (1 ≤ N ≤ 16)

둘째 줄부터 N개의 줄에 걸쳐 N×N 크기의 비용 행렬 $P$가 주어진다. 각 줄은 N개의 정수로 이루어져 있다. $P[i][j]$는 가동 중인 발전소 $j$를 이용해 정지된 발전소 $i$를 가동시킬 때 드는 비용을 의미한다. (0 ≤ $P[i][j]$ ≤ 50)

다음 줄에 각 발전소의 현재 상태가 길이 N의 문자열로 주어진다. $i$번째 문자가 'Y'이면 $i$번 발전소가 가동 중임을, 'N'이면 정지 상태임을 나타낸다.

마지막 줄에 목표로 하는 최소 가동 발전소 수 P가 주어진다. (0 ≤ P ≤ N)

출력

적어도 P개의 발전소를 가동시키기 위한 최소 비용을 출력하라.

• 이미 가동 중인 발전소의 수가 P개 이상이면 0을 출력한다.
• 모든 발전소가 정지 상태('N')이고 P가 1 이상이라면 새로 가동시킬 수 없으므로 -1을 출력한다.
• 가동 중인 발전소가 있지만 목표 수 P를 달성할 수 없는 경우에도 -1을 출력한다.

입출력 예시

입력 1

3
0 10 11
10 0 5
11 5 0
YNY
2

출력 1

5

입력 2

3
0 10 11
10 0 5
11 5 0
YNY
3

출력 2

-1

입력 3

3
0 10 11
10 0 5
11 5 0
NNN
0

출력 3

0