Maze With Teleport Pads

A puzzle maze is a list of equal-length strings maze. '.' is floor, '#' is a wall, and a lowercase letter is a floor tile carrying a teleport pad. You start in the top-left cell and want the bottom-right cell (neither is a wall).

Walking to an adjacent (up/down/left/right) non-wall cell costs 1. While standing on a pad with letter x, you may teleport to any other pad with the same letter for a cost of jump.

Return the minimum total cost to reach the exit, or -1 if it is impossible.

Examples

Input:  maze = ["..b",
                "###",
                "b.."], jump = 3
Output: 7
Explanation: walk 2 steps to the top-right 'b', teleport (3), walk 2 steps.

Input:  maze = ["a.#",
                "##.",
                "..a"], jump = 5
Output: 5
Explanation: the start and exit are both 'a' pads; walking is impossible.

Constraints

• 1 <= rows, cols and rows * cols <= 4 * 10**4, 0 <= jump <= 10**4
• Target O(R * C * log(R * C)) time.

Goals

• Combine ordinary grid moves with 'jump to any matching pad' moves
• Expand each pad group only once to avoid quadratic work
• Return -1 when the exit is unreachable