Thumb 5b3

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

55.6% (5/9)



As you know, Doraemon likes to eat Dorayaki very much,
actually, the number of Dorayaki he eats a day over 1000000!

BUT! Because he spends too much on Dorayaki, he is now a poor poor poor poor poor robat cat.
After selling a lot of items for money in order to buy more Dorayaki, he is now nothing more than a old robat cat. O_Q

One day, he found a map which tells some position of Dorayaki,
and he decided to eat Dorayaki on the map as much as possible.

At the beginning, Doraemon is at home and he has some heals point HP.
If he eats a Dorayaki, he can get some heals point G.

When Doraemon wants to eat a Dorayaki,
he leave home and go to the position of the Dorayaki,
this will spend D heals point. (D is the manhattan distance between his home and the Dorayaki)
then he eat the Dorayaki and get G heals point.
Finally, he go back home.(this costs D heals point.)

Notice that when Doraemon's heals point become zero, he will die immediately.

Doraemon would like to know what's the maximum number of Dorayaki he can eat and then go back home safety(still alive!),
can you help him?

Input Format

There is a postive integer number T at the first line.
Then T testcases, and there will be 4 non-negative integers at the first line of each testcases,
H, W, HP, G.(1<=H,W<=1000)
and then H lines, each line has W characters.

"e" means there is a Dorayaki.
"D" means that is Doraemon's home.
"." means there is nothing.

Output Format

You should output T lines, the maximum number of Dorayaki Doraemon can eat respectively.

Sample Input

5 5 3 1
5 5 3 1

Sample Output



For two position (x1,y1) (x2,y2),
the manhattan distance between these two positions is |x1-x2|+|y1-y2|.

Problem Source

原TIOJ1584 / Problem Setter: akira


No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1