Fire Drill

Joko is taking part in a fire drill organized by the Jakarta Fire Department to recruit new firemen. In the drill, a candidate must rescue volunteers (who act as unconscious people) trapped inside a building within a limited amount of time. The building has several floors, and the volunteers are scattered throughout it. Each volunteer is worth a certain number of points.

The candidate rescues a volunteer by carrying her to the exit, and earns that volunteer's points once she is delivered.

Each floor is a grid of cells. A cell is an obstacle, empty space, a stair, or the entry/exit point.

The candidate starts at the entry point, which is a single cell on the first floor. In one second the candidate can move to any adjacent non-obstacle cell (north, south, west, or east) or climb one stair up or down. While carrying a volunteer, each such move instead takes two seconds. When the candidate reaches a volunteer he may choose whether to rescue her; if he does, he must carry her straight to the exit without stopping, and he can carry at most one volunteer at a time.

Given the floor plan, help Joko plan his moves so that he earns the highest possible total score.

The first line contains an integer $T$ ($T \le 100$), the number of test cases.

Each test case begins with five integers $L$, $H$, $W$, $N$, and $S$, where $1 \le L \le 10$, $1 \le H \le 100$, $1 \le W \le 100$, $1 \le N \le 100$, and $1 \le S \le 10000$. They denote the number of floors, the height (rows) and width (columns) of every floor, the number of unconscious people, and the available time in seconds, respectively.

The next $L$ blocks describe the floors from the 1st floor up to the $L$th floor. Each floor is given as $H$ lines of $W$ characters. The characters are:

• S: the starting point, which also serves as the exit. It appears exactly once and only on the first floor.
• X: an obstacle that cannot be entered (wall, fire, etc.).
• U: a stair connecting to the floor above. The cell directly above it holds a D. This character never appears on the highest floor.
• D: a stair connecting to the floor below. The cell directly below it holds a U. This character never appears on the lowest floor.
• .: empty space that can be entered.

The next $N$ lines each contain four integers $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$), giving a volunteer's floor, row, column, and point value. Every volunteer stands on empty space, and no two volunteers share a cell.

For each test case, print a single line containing the maximum total points the candidate can earn by rescuing people within the given time.