Fastest commute on a mode grid

A city map is a grid, given as a list of equal-length strings (or lists of one-character strings). Each cell is one of:

• 'S': home. There is exactly one.
• 'D': the office. There is exactly one.
• 'X': blocked.
• a digit '1' .. '9': a street that only mode d can use (mode d is index d - 1 in the lists below).

You also get modes (names), times and costs, all of length k (1 <= k <= 9). Every digit in the grid is at most k. Moving onto a mode-d cell takes times[d-1] minutes and costs[d-1] dollars. Stepping onto 'S' or 'D' is free.

Moves go up, down, left or right. In this level you pick one mode for the whole trip, and the path may only use cells of that mode between S and D. A trip has to use at least one street cell, so S right next to D does not count as a trip by itself.

Write fastest_mode(grid, modes, times, costs) -> str. Return the name of the mode with the smallest total time. Break ties by smaller total cost, then by the earlier mode in the list. Return "" if no mode can make the trip.

grid = ["S111D",
        "2222X"]
fastest_mode(grid, ["walk", "tram"], [4, 2], [0, 3])   # "walk": 3 cells x 4 = 12 min
# the tram cells never reach D

Grids can be up to 400 × 400.