Problem E
Kattis' Little Helpers

Picture by Martin Fisch via Flickr, cc by-sa

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.

For the purposes of this problem, cyberspace is a rectangular grid, in which catbots can move up, down, left, and right. Some squares in the grid are impassable walls. All catbots start at Kattis HQ, and must end at Kattis HQ after all the tasks are done. Your task is to write a program to find the minimum total number of steps, given the map of cyberspace and the tasks that need to be done. A task is considered performed if there is a catbot in the location of the task after the previous task has been performed. E.g., if we first move a catbot to the location of the second task, and then a catbot to the location of the first task, then both the tasks have been performed – the first catbot does not need to re-enter the location of the second task in order to perform it.

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.

Figure 1: Illustration of Sample Input 1.

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.

5 4 2 3
.....
...K.
.....
.....
1 1
5 1
1 4

16

5 4 2 3
.....
###K.
.....
.....
1 1
5 1
1 4

20

4 4 20 3
.K..
.#..
#.#.
.#..
1 1
2 3
1 1

impossible