밟힌 케이블

Nathan O. Davis는 회사를 운영하고 있다. 그의 회사는 사용자가 많은 웹 서비스를 운영하며, 사무실은 서버와 라우터, 그리고 엉킨 LAN 케이블로 가득하다.

그는 엉킨 케이블 때문에 골머리를 앓고 있다. 케이블은 여러 가지 문제를 일으킨다. 예를 들어, 회사 직원들은 종종 케이블에 걸려 넘어진다. 케이블이 연결되어 있지 않으면 다칠 일은 없다. 그저 운이 좋은 것이다. 케이블이 연결되어 있으면 컴퓨터가 넘어져 고장 날 수도 있다. 그는 새 컴퓨터와 새 케이블을 들여올 예정이다. 그는 직원들이 새 케이블을 밟는 횟수를 최소화하려고 한다.

그의 사무실은 H \times W개의 칸으로 이루어진 2차원 격자로 배치되어 있다. 새 케이블은 칸의 변을 따라 놓여야 한다. 케이블의 양 끝은 칸의 꼭짓점에 위치한다. 격자는 왼쪽 위 꼭짓점이 (0, 0)인 0부터 시작하는 좌표로 표현된다.

각 직원은 특정 칸 안에서 업무를 시작하고, 매일 정해진 규칙에 따라 격자를 따라 반복적으로 이동한다. 이동 규칙은 U, D, L, R 네 문자의 문자열로 주어진다. U는 위로 이동, D는 아래로 이동, R은 오른쪽으로 이동, L은 왼쪽으로 이동을 의미한다. 예를 들어 UULLDDRR은 위, 위, 왼쪽, 왼쪽, 아래, 아래, 오른쪽, 오른쪽으로 순서대로 이동하는 것을 의미한다. 직원은 이 규칙을 정확히 T번 반복한다. 직원이 격자 밖으로 나가려 하면 그 칸에 그대로 머문다.

모든 직원의 이동 규칙과 새 케이블 양 끝의 위치가 주어진다. 새 케이블을 최적으로 배치하여, 직원들이 케이블을 밟는 총 횟수를 최소화하는 값을 구하라.

입력의 첫 줄에는 사무실의 크기 W, H (1 ≤ W, H ≤ 500)와 직원 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 줄에는 연결할 LAN 케이블의 두 끝점의 위치를 나타내는 두 개의 x-y 쌍 (0 ≤ x ≤ W, 0 ≤ y ≤ H)이 주어진다. 이 값은 케이블이 칸의 왼쪽 위 꼭짓점에 꽂히는 좌표를 나타낸다. 예외적으로 x = W는 가장 오른쪽 칸의 오른쪽 변을, y = H는 가장 아래 칸의 아래쪽 변을 의미한다.

다음 줄부터는 직원의 초기 위치와 이동 규칙이 주어진다. 첫 줄에는 직원의 초기 칸 좌표를 나타내는 x-y 쌍 (0 ≤ x ≤ W, 0 ≤ y ≤ H)이 주어진다. 다음 줄에는 정수 T (1 ≤ T ≤ 100)와 위에서 설명한 의미를 가지는 U, D, L, R로 이루어진 문자열이 주어진다. 규칙 문자열의 길이는 1 이상 1,000 이하이다. 이 두 줄이 N번 반복된다.

직원들이 케이블을 밟는 최소 총 횟수를 한 줄에 출력한다.