Clone Robot

Sejun built a robot that can clone itself into any number of identical robots. Cloning devices are installed only at the robot's starting cell and at the cells containing keys.

You are given an N × N square maze, the positions of M keys, and the robot's starting position. Find the minimum possible total number of moves made by all robots until every key is found.

A robot can move one cell at a time in the four cardinal directions. When any robot reaches a cell containing a key, that key is considered found. Multiple robots may occupy the same cell at the same time, and a cell that has already been visited may be visited again by any robot. Cloning takes no time. After all keys are found, the robots do not need to gather at one position.

The first line contains the maze size N and the number of keys M, separated by a space. (4 ≤ N ≤ 50, 1 ≤ M ≤ 250)

The next N lines describe the maze. Each character is one of 1, 0, S, and K.

• 1: wall
• 0: passable cell
• S: robot's starting position
• K: key position

There is exactly one S and exactly M cells marked K. Cloning is possible only on cells marked S or K. Every border cell of the maze is a wall.

Print the minimum total number of moves made by all robots to find every key. If it is impossible to find every key, print -1.