Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3698
Carrot Fantasy

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Carrot Fantasy is a tower-defense game on mobile phone. To get the victory, you need to build different towers to protect the cute carrot from being eaten by monsters. The game is played on a map with m*n grids. There will be totally k monsters trying to rush to your carrot. To simplify this game, we assume that the monsters will be born one by one on a fixed grid. In each second, there is one monster born on the map and the monster cannot move until the next second. Each monster can only move 1 grid in 1 second. In each second, monsters will move first, then the tower start shooting (see the sample and hint for a better understanding of this rule). Notice that the game ends immediately if any monster reaches the carrot's grid.

In this problem, there are 4 types of towers, which are listed below:

Bottle Tower: A bottle tower can attack a single monster that stands on one of its adjacent grids. Two grids are adjacent if they share a common edge or corner. A monster shot by bottle tower will lose 10 HP.

Fire Tower: A fire tower can attack all monsters standing on its 8 adjacent grids simultaneously. The damage of fire tower is 10 HP.

Needle Tower: A needle tower can attack a single monster that stands on one of its adjacent grids. If a monster is shot by the needle tower, it will be poisoned forever. In each second, a poisoned monster will lose 10 HP before it moves. If a poisoned monster is shot by a needle tower again, the poison effect does not change.

Ice Tower: An ice tower can attack a single monster that stands on one of its adjacent grids. If a monster is shot by the ice tower, it will be frozen for 1 second (which means it cannot move in the next second). If a frozen monster is shot by an ice tower again, the freezing effect does not change.

All towers can only attack once for every second and they will attack at the same time. A monster will be killed if it has no more than 0 HP. Towers (except the fire tower) will always choose to attack the monster which is nearest to the carrot. Here "nearest" means the monster will be the earliest one to reach the grid of carrot if it is not killed or frozen. If there are two or more "nearest" monsters, towers will choose to attack the monster born on the map earliest.

Now given the position of your towers and the information of monsters, please calculate how many seconds you need to kill all monsters.

Input

The first line of input is an integer T (T <= 200) indicating the number of test cases. For each case, first there is a line containing 4 integers: m, n, k, h (0 < m, n <=15, 0 < k, h <= 50) with m and n indicating the size of the map, k indicating the number of monsters, h indicating the HP of each monster. Then there are m lines each containing n characters to describe the map. In the map, 'X' stands for stone grid, '.' stands for empty grid, 'S' stands for monster's born grid, 'T' stands for the carrot, 'B' stands for the bottle tower, 'F' stands for the fire tower, 'N' stands for the needle tower, 'I' stands for the ice tower. Monsters can only move on empty grid in one of the 4 directions: north, south, east and west. We guarantee that the route of monsters is unique which means there is only one way leading to the carrot. Please notice that there might be two or more monsters standing on the same grid.

Output

For each case, output a single line with an integer indicating the time you need to kill all monsters. If you cannot kill all monsters, just output -1 in a single line.

Sample Input

4
2 2 1 50
ST
IB
2 2 2 20
ST
FN
4 4 10 10
S...
XXB.
XXX.
T...
4 4 10 10
S...
XXX.
XXX.
T...

Sample Output

5
3
11
-1

Hint

For case 1, in the 1st second, the monster born on the map and he can eat the carrot immediately in the next second! Unfortunately, in the 1st second, the monster is frozen by ice tower and it cannot move in the next second! So it just stays there and the bottle tower needs 5 seconds to kill it.

For case 2, the monster is shot by the fire tower in the 1st second with only 10 HP left. It is also poisoned by needle tower. Then in the 2nd second, the poison deals 10 damage before the monster move and makes it die. The same thing will happen to the monster born in the 2nd second. So the answer is 3.


Author: HUANG, Qiao
Contest: The 13th Zhejiang University Programming Contest
Submit    Status