벼룩

격자 칸마다 접착제를 붙여 직사각형 모양의 벼룩 덫을 만들었습니다. 각 접착제에는 약한 방향이 있습니다. 접착제 위에 있는 벼룩이 약한 방향으로 뛰면 접착제에서 벗어날 수 있습니다.

더 정확히 말하면, 각 접착제는 U, D, L, R 중 하나로 표시되며 각각 위, 아래, 왼쪽, 오른쪽을 뜻합니다.

벼룩은 한 번에 최대 $K$칸까지 뛸 수 있습니다. 벼룩이 직사각형 밖으로 뛰쳐나가면 그 벼룩이 탈출했다고 합니다.

덫의 어떤 칸에 놓인 벼룩이 연속으로 뛰어서 탈출할 수 있으면, 그 칸을 탈출 가능한 칸이라고 합니다. 탈출 가능한 칸의 개수를 구하세요.

첫 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어집니다.

이어지는 $N$개의 줄에는 각 칸의 약한 방향을 나타내는 길이 $M$의 문자열이 한 줄씩 주어집니다.

탈출 가능한 칸의 개수를 출력합니다.

• $N$, $M$, $K$는 정수이다.
• $1\le N\le 2\,000$
• $1\le M\le 2\,000$
• $1\le K\le 2\,000$
• 각 문자열은 U, D, L, R로만 이루어져 있다.