소방 훈련

조코(Joko)는 신입 소방관을 뽑기 위해 자카르타 소방서가 여는 소방 훈련에 참가한다. 이 훈련의 목표는 제한된 시간 안에 건물 안에 갇힌 자원봉사자(의식을 잃은 사람 역할)를 구조하는 것이다. 건물은 여러 층으로 이루어져 있고, 자원봉사자들은 건물 곳곳에 흩어져 있다. 각 자원봉사자에게는 점수가 매겨져 있다.

지원자는 자원봉사자를 출구까지 업고 나와야 구조한 것으로 인정되며, 구조에 성공하면 그 자원봉사자의 점수를 얻는다.

각 층은 칸으로 이루어진 격자이다. 한 칸은 장애물, 빈 공간, 계단, 또는 입구/출구 중 하나이다.

지원자는 1층에 단 하나만 존재하는 입구 칸에서 출발한다. 1초 동안 지원자는 인접한(북, 남, 서, 동) 장애물이 아닌 칸으로 이동하거나 계단을 한 층 오르내릴 수 있다. 자원봉사자를 업고 있는 동안에는 이러한 이동 한 번이 2초 걸린다. 지원자가 자원봉사자가 있는 칸에 도착하면 그를 구조할지 말지 선택할 수 있는데, 구조하기로 했다면 도중에 멈추지 않고 곧바로 출구까지 업고 나와야 한다. 또한 한 번에 최대 한 명만 업을 수 있다.

건물의 평면도가 주어질 때, 조코가 얻을 수 있는 최대 점수를 계산하도록 도와주자.

첫 줄에 테스트 케이스의 수를 나타내는 정수 $T$ ($T \le 100$)가 주어진다.

각 테스트 케이스는 다섯 정수 $L$, $H$, $W$, $N$, $S$로 시작한다. 여기서 $1 \le L \le 10$, $1 \le H \le 100$, $1 \le W \le 100$, $1 \le N \le 100$, $1 \le S \le 10000$이며, 각각 층 수, 모든 층의 세로 길이(행 수)와 가로 길이(열 수), 의식을 잃은 사람의 수, 주어진 시간(초)을 의미한다.

다음으로 1층부터 $L$층까지 각 층의 지도가 $L$개의 블록으로 주어진다. 각 층은 $W$개의 문자로 이루어진 $H$개의 줄로 표현된다. 사용되는 문자는 다음과 같다.

• S: 출발 지점이며 동시에 출구이다. 정확히 한 번만, 그리고 오직 1층에만 나타난다.
• X: 들어갈 수 없는 장애물(벽, 불 등).
• U: 위층으로 연결되는 계단. 바로 위층의 같은 위치에는 D가 있다. 이 문자는 가장 높은 층에는 나타나지 않는다.
• D: 아래층으로 연결되는 계단. 바로 아래층의 같은 위치에는 U가 있다. 이 문자는 가장 낮은 층에는 나타나지 않는다.
• .: 들어갈 수 있는 빈 공간.

이어서 $N$개의 줄에 각각 네 정수 $f_i$, $r_i$, $c_i$, $p_i$ ($1 \le f_i \le L$, $1 \le r_i \le H$, $1 \le c_i \le W$, $1 \le p_i \le 1000$)가 주어지며, 이는 한 자원봉사자의 층, 행, 열, 점수를 나타낸다. 모든 자원봉사자는 빈 공간에 있으며, 두 자원봉사자가 같은 칸에 있는 경우는 없다.

각 테스트 케이스마다, 주어진 시간 안에 사람들을 구조하여 얻을 수 있는 최대 점수를 한 줄에 하나의 정수로 출력한다.