Pohang Hang

While browsing Everytime, you saw a post!

Terrified by this post, you decide to run to the nearby restaurants that sell gwamegi. But gwamegi is so popular these days that each restaurant sells only one serving. So you must visit five restaurants in total to eat gwamegi. You are starting to chuckle, saying pohang hang hang. Let's eat the gwamegi as fast as possible and break the curse!

You are given a map of size $N \times M$. On the map, your position is given as 'S' and the positions of restaurants are given as 'K'. Obstacles exist here and there on the map, and they are given as 'X'. You can move one cell at a time up, down, left, or right, and moving one cell takes 1 minute. You cannot move onto a cell with an obstacle.

Print the minimum time needed to visit 5 restaurants.

The first line gives $N, M \, (4 \leq N, M \leq 1,000)$.

After that, $N$ lines follow, each giving a string of length $M$.

'.' is an empty cell, 'X' is an obstacle, 'S' is your current position, and 'K' is a restaurant ($1 \leq$ number of restaurants $\leq 20$).

Starting from 'S', print the minimum time needed to visit 5 of the given restaurants. If you cannot visit 5 restaurants, print $-1$.

In the first example, you can visit 5 restaurants by moving 3 cells right, 1 cell left, 3 cells down, 1 cell right, and 3 cells left, for a total of 11 cells.

In the second example, obstacles block the way, so you cannot visit 5 restaurants.