ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Internal Contest March'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Die Hard

Time limit: 5.0 second
Memory limit: 64 MB
Problem illustration
There is a city with a grid of square blocks of the N × M size. There are buildings in some blocks, some blocks are blank. John is in the block (x0, y0). He may move from a block to an adjacent one in horizontal, vertical or diagonal direction with velocity V. He is told over the radio the list of points where bombs are located. John is to disarm them in the same order that they follow in the list or he will die hard with a vengeance. If he can't reach some bomb he moves to the next one. All the bombs are located outside the buildings.
What minimal time will John need to finish his job if he disarms a bomb immediately?

Input

The first line contains numbers N, M, K (an amount of bombs) and V, separated with a space, satisfying the restrictions 1 ≤ N, M ≤ 75; 1 ≤ K ≤ 1000; 0.01 < V < 10.00. Then a city map follows: M lines of N symbols. The symbol '.' means a blank block, '#' stands for a building. Then follow the line that contains coordinates (x0, y0). The input is ended by K lines with bombs coordinates in that very order that John passed them.

Output

You should output the single number which is the minimal time necessary to do the job. The time should be printed with two digits after a decimal point.

Sample

inputoutput
4 3 3 1.23
....
##..
....
1 1
1 3
4 1
4 3
8.66
Problem Author: Pavel Atnashev
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
To submit the solution for this problem go to the Problem set: 1254. Die Hard