Power Plants

Interview

Time limit2sMemory limit128 MB

Summary

Given restart costs between plants and which plants are already on, find the minimum total cost to reach at least P working plants, or -1.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Greedy, Graph
Solved: No attempts yet

Problem

Eunjin works at a power plant facility. While she briefly fell asleep, several power plants broke down, and her boss is now walking toward her office. She must restore enough plants before the boss arrives.

A broken plant can be restarted by using a plant that is already working. The restart cost depends on which working plant is used and which broken plant is restarted.

Find the minimum total cost needed to make at least P power plants working.

Input

The first line contains the number of power plants, N. N is a positive integer no greater than 16.

The next N lines contain the cost matrix. The j-th value on the i-th line is the cost of restarting plant j by using plant i.

The following line contains a string of length N describing the current state of each plant. Y means the plant is on, and N means it is off.

The last line contains the target count P. Every cost is a nonnegative integer no greater than 36, and P is an integer from 0 to N.

Output

Print the minimum cost required to make at least P plants working. If it is impossible, print -1.

Examples5

Example 1
Input
```
3
0 10 11
10 0 12
12 13 0
YNN
3
```
Expected output
```
21
```
Example 2
Input
```
3
0 2 4
2 0 3
4 3 0
YNN
3
```
Expected output
```
5
```

Example 3

Input

5
1 10 11 12 13
3 5 17 15 8
15 13 22 3 1
10 22 14 9 3
0 1 3 9 0
NYNNN
5

Expected output

Example 4
Input
```
3
0 1 2
1 2 3
2 3 4
NNY
2
```
Expected output
```
2
```

Example 5

Input

7
1 3 0 9 3 2 8
13 28 2 3 8 9 30
9 2 14 19 15 10 23
9 2 8 15 19 23 28
15 19 28 0 13 19 15
9 15 32 19 32 0 14
2 3 19 15 23 15 28
YYNYYNY
4

Expected output