Kattis

Kattis' Little Helpers

Picture by Martin Fisch via Flickr, cc by-sa
It is not an easy life being an online judge. Kattis has lots of things to do and sometimes all her tasks can be overwhelming. For instance, to judge a submission, Kattis has to run all over cyberspace to figure out an appropriate verdict. First she has to go to Compiler Plaza and haggle with the merchants there to see if anyone is willing to compile the source code for her. Next she needs to go to the Data Market to pick up some fresh test cases to feed to the submission. With these things done she goes to the CPU track to let the code run for a while. Then she may have to do a quick stop at the hospital to patch the submission up in case it crashed. And it seems like it will never stop...

But help is on its way! Kattis has recently acquired a number of programmable catbots, which she can send off on all these errands instead of going herself. Each catbot is equipped with a top-of-the-line MeowFi antenna, with which it can instantly transfer any materials it picks up at a location to all the other catbots. This means that different catbots could visit the different locations, as long as the locations are visited in order.

Kattis is very concerned about the future of our planet, and wants to perform her task in a resource-efficient way. The main resource used in this process is the energy needed for the catbots to move from place to place. Thus, Kattis wants to minimize the total number of steps taken by all the catbots.

Consider a grid as in Figure 1 below, with access to two catbots and three places to visit. A good sequence of moves would then be to send the first catbot to location $1$ ($4$ steps), then the other catbot to location $2$ ($2$ steps), then the first catbot from location $1$ to location $3$ ($3$ steps) and finally to send both catbots home again ($5+2$ steps), for a total of $16$ steps.

Input

The first line of input consists of four integers $w$, $h$, $c$, and $t$ ($1 \le w, h, c, t \le 200$), where $w$ is the width and $h$ is the height of the cyberspace grid, $c$ is the number of catbots that Kattis has bought, and $t$ is the number of tasks that need to be performed.

Then follow $h$ lines, each containing $w$ characters, giving a map of cyberspace. Each character is either a ‘#’ indicating an impassable wall, a ‘K’ indicating Kattis HQ, or a ‘.’ for the remaining positions. There is exactly one ‘K’ in the grid.

Then follow $t$ lines. The $i^\textrm {th}$ of these lines contains two integers $x_ i$ and $y_ i$ ($1 \le x_ i \le w$, $1 \le y_ i \le h$) indicating that the $i^\textrm {th}$ location to visit is in column $x_ i$ of row $y_ i$ of the grid. The positions of these locations are not necessarily distinct, but will neither be walls nor Kattis HQ.

Output

Output the minimum total number of steps needed for the catbots to visit all the locations in order and return to Kattis HQ, or “impossible” if it is not possible to visit all the locations.

Sample Input 1 Sample Output 1
5 4 2 3
.....
...K.
.....
.....
1 1
5 1
1 4

16

Sample Input 2 Sample Output 2
5 4 2 3
.....
###K.
.....
.....
1 1
5 1
1 4

20

Sample Input 3 Sample Output 3
4 4 20 3
.K..
.#..
#.#.
.#..
1 1
2 3
1 1

impossible