Maze Repair

Interview

Time limit2sMemory limit1024 MB

Summary

Each cell points to a neighbor or outside the grid. Find the minimum cost of jump pads so that every starting cell escapes, which means hitting every cycle.

Level: Medium4 of 10
Topics: Graph, Implementation
Solved: No attempts yet

Problem

A maze is an $N \times M$ grid with $N$ rows and $M$ columns. Each cell shows one of 'up', 'down', 'left', or 'right'. Anyone who arrives at a cell moves one cell in the direction shown there. Repeating this, a person escapes once they leave the maze.

The blue path in the figure is an escape. With bad luck, though, a person can follow the red path in the figure and never leave. To prevent this, Hyungjin decides to repair the maze.

Hyungjin can install as many jump pads as he wants. Anyone who arrives at a cell with a jump pad leaves the maze immediately by jumping out.

Installing a jump pad costs a different amount depending on the cell. Installing a jump pad in the cell at row $i$ , column $j$ costs $Cost_{i,j}$ .

Find the minimum total cost of installing jump pads so that a person starting from any cell in the maze can escape.

Input

The first line contains $N$ and $M$ separated by a space.

The next $N$ lines each contain a string of length $M$ . The string uses only the uppercase letters U, D, L, and R, meaning up, down, left, and right.

The next $N$ lines each contain $M$ integers $Cost_{1,1}$ $Cost_{1,2}$ $\cdots$ $Cost_{1,M}$ , and so on, separated by spaces. These give the cost of installing a jump pad in each cell.

Output

Print the minimum total cost of installing jump pads so that a person starting from any cell can escape the maze.

Constraints

$1 \leq N, M \leq 2000$
$1 \leq Cost_{i,j} \leq 500$

Examples2

Example 1
Input
```
3 3
LLL
DLU
RUU
3 1 5
2 9 6
8 7 1
```
Expected output
```
2
```
Example 2
Input
```
2 4
RDDL
ULRU
2 2 20 20
2 2 20 20
```
Expected output
```
22
```