class VampiresWalk
{
  public:
    bool visited[22][22][6][1 << 8];
    int getMinTime( vector<string> maze )
    {
        int n = maze.size();
        int m = maze[0].size();

        int si, sj;
        int prey = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(maze[i][j] == 'V') {
                    si = i;
                    sj = j;
                }
                if(maze[i][j] == 'K') {
                    maze[i][j] = (prey + '0');
                    prey++;
                }
            }
        }
        memset(visited, false, sizeof visited);
        queue<int> q;
        q.push(si);
        q.push(sj);
        q.push(5);
        q.push(0);
        q.push(0);
        visited[si][sj][5][0] = true;
        int di[] = {-1, 1, 0, 0};
        int dj[] = {0, 0, -1, 1};
        while(!q.empty()) {
            int ci = q.front(); q.pop();
            int cj = q.front(); q.pop();
            int layers = q.front(); q.pop();
            int bitmask = q.front(); q.pop();
            int dist = q.front(); q.pop();

            if(bitmask == (1 << prey) - 1) {
                return dist;
            }
            for(int i = 0; i < 4; i++) {
                int ti = ci + di[i];
                int tj = cj + dj[i];

                if(ti >= 0 and tj >= 0 and ti < n and tj < m) {
                    if(maze[ti][tj] == '.' and !visited[ti][tj][layers][bitmask]) {
                        q.push(ti);
                        q.push(tj);
                        q.push(layers);
                        q.push(bitmask);
                        q.push(dist + 1);
                        visited[ti][tj][layers][bitmask] = true;
                    }
                    if(maze[ti][tj] == '*' and layers > 0 and !visited[ti][tj][layers - 1][bitmask]) {
                        q.push(ti);
                        q.push(tj);
                        q.push(layers - 1);
                        q.push(bitmask);
                        q.push(dist + 1);
                        visited[ti][tj][layers - 1][bitmask] = true;
                    }
                    if(maze[ti][tj] == 'P' and !visited[ti][tj][5][bitmask]) {
                        q.push(ti);
                        q.push(tj);
                        q.push(5);
                        q.push(bitmask);
                        q.push(dist + 1);
                        visited[ti][tj][5][bitmask] = true;
                    }
                    if(isdigit(maze[ti][tj])) {
                        int id_prey = (maze[ti][tj] - '0');
                        int new_mask = (bitmask | (1 << id_prey));
                        if(!visited[ti][tj][layers][new_mask]) {
                            q.push(ti);
                            q.push(tj);
                            q.push(layers);
                            q.push(new_mask);
                            q.push(dist + 1);
                            visited[ti][tj][layers][new_mask] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
};