Cave Exploration

Several explorers are standing at the entrance of a cave. The goal is to get every explorer through the cave so that they all end up on the exit side.

A map is required inside the cave, but there is only one map. Therefore, each moving group must carry the map, and the next move must start from the side where the map currently is. An explorer who is already on the exit side may return to the entrance side to bring the map back.

During the trip, the explorers must cross an old bridge. All explorers in one group cross the bridge at the same time, and the total weight of the group must not exceed the bridge limit B.

An explorer may move alone. A group of two or more explorers may move together only if every explorer in the group trusts at least one other explorer in that same group.

Explorers walk at different speeds. When a group moves together, the time spent is the walking time of the slowest explorer in that group.

Find the minimum total time needed to move all explorers to the exit side.

The first line contains the number of explorers N. N is a positive integer not greater than 13.

Each of the next N lines contains the weight and walking time of one explorer. Both values are positive integers not greater than 1,000.

The next N lines describe the trust relation. If the j-th character of the i-th line is Y, explorer i trusts explorer j; if it is N, explorer i does not trust explorer j. The i-th character of the i-th line is always Y. The relation does not have to be symmetric.

The last line contains the bridge weight limit B. B is a positive integer not greater than 5,000.

Print the minimum time required for all explorers to reach the exit side. If it is impossible, print -1.

In the first public test, explorers 1 and 3 move to the exit side, explorer 1 returns alone to the entrance side, and then explorers 1 and 2 move to the exit side. The total time is 4 + 2 + 3 = 9.