미로 보수

미로는 세로 $N$칸, 가로 $M$칸으로 이루어진 $N \times M$ 격자다. 각 칸에는 '상', '하', '좌', '우' 중 하나가 적혀 있다. 칸에 도착한 사람은 그 칸에 적힌 방향으로 한 칸 이동한다. 이를 반복하다 미로 밖으로 나가면 탈출한 것이다.

그림의 파란색 경로는 탈출하는 예시다. 하지만 운이 나쁘면 그림의 빨간색 경로처럼 영원히 탈출하지 못할 수도 있다. 이를 막기 위해 형진이는 미로를 보수하기로 했다.

형진이는 미로에 원하는 만큼 점프대를 설치할 수 있다. 점프대가 설치된 칸에 도착한 사람은 점프해서 바로 미로 밖으로 나온다.

점프대를 설치하는 비용은 칸마다 다르다. $i$행 $j$열 칸에 점프대를 설치하는 데 $Cost_{i,j}$의 비용이 든다.

미로의 어느 칸에서 출발하더라도 탈출할 수 있도록 점프대를 설치하려 한다. 필요한 최소 비용을 구하라.

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.

이어 $N$개의 줄에 걸쳐 길이가 $M$인 문자열이 주어진다. 문자열은 대문자 U, D, L, R로만 이루어져 있으며, 각각 상, 하, 좌, 우를 뜻한다.

이어 $N$개의 줄에 걸쳐 각 칸에 점프대를 설치하는 비용이 공백을 사이에 두고 주어진다. 즉 $Cost_{1,1}$ $Cost_{1,2}$ $\cdots$ $Cost_{1,M}$ 형식으로 $M$개씩 주어진다.

미로의 어느 칸에서 출발하더라도 탈출할 수 있도록 점프대를 설치할 때의 최소 총 비용을 출력한다.

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