Forager

$Forager$ is a pixel style 2D adventure game, players can do farming, do fishing, kill monsters and cut trees etc. In addition, some temples will appear in some lands, you can explore them and get a lot of items. Mr. D is interested in this game recently and has no intention to train on algorithm.

Today, Mr. D goes to The Frost Temple in $Forager$ and finds lots of ray sources, turning stones and gem stones. The Frost Temple can be considered as an $n \times m$ map, each grid may be empty, ray source, turning stone, gem stone or wall. The characteristics of each item are listed below.

$\qquad \cdot$ Empty grid. The ray can go through it directly, multiple rays are allowed to go through it.

$\qquad \cdot$ Ray source. A ray source can shoot a beam of ray in a certain direction (up, down, left or right), and also can be passed like an empty gird.

$\qquad \cdot$ Turning stone. It can absorb light from all directions to it and shoot it in a certain direction (up, down, left or right). It costs you some value to rotate the shoot direction 90 degrees clockwise.

$\qquad \cdot$ Gem stone. It has a lot of treasures but the value of a gem stone can be taken if and only if there is a beam of ray to it, and it does not disappear after you take its value. It can stop ray from all directions, which means that the ray can't go through it. The value of a gem stone can only be taken at most once.

$\qquad \cdot$ Wall. It can stop ray from all directions, it means that the ray can't go through it.

Mr. D can rotate some turning stones (if needed) and get the value of some gem stones. He has not trained for algorithm for a long time, but he wants to get the value as much as possible, so he is asking for your help.

Given the map of The Frost Temple, you should tell Mr. D the maximum value he can earn.

Note: Mr. D has infinite value.

First line contains a single integer $T(1 \le T \le 20)$ representing the number of test cases.

For each case:

The first line contains four integers $n, m, k, l$ $(1 \le n, m \le 50, 0 \le k, l \le n \times m)$, represents the size of the Frost Temple, the number of gem stones and the number of turning stones.

The following $n$ lines, each line contains $m$ characters, represents the map of the Frost Temple. For each character:

$\qquad \cdot$ '.' represents the empty grid.

$\qquad \cdot$ 'U'', 'D', 'L', 'R' represents there's a ray source, and the direction of it (up, down, left or right).

$\qquad \cdot$ '$\wedge$' (the character above '6' on the keyboard), 'v', '<', '>' represents there's a turning stone, and the initial direction of it (up, down, left or right), its cost is given in the following $l$ lines.

$\qquad \cdot$ 'x' represents there's a gem stone, its value is given in the following $k$ lines.

$\qquad \cdot$ '#' represents there's a wall.

The following $k$ lines, each line contains three integers $x_{i}, y_{i}, v_{i}$ $(1 \le x_{i} \le n, 1 \le y_{i} \le m, 0 \le v_{i} \le 10^{9})$, representing that the value of $(x_{i}, y_{i})$ is $v_{i}$.

The following $l$ lines, each line contains three integers $x_{i}, y_{i}, z_{i}$ $(1 \le x_{i} \le n, 1 \le x_{i} \le m, 0 \le c_{i} \le 10^{9})$, representing that the cost of $(x_{i}, y_{i})$ is $c_{i}$.

It is guaranteed that all the positions appear in the last $k+l$ lines are distinct.

For each test, output an integer represents the maximum value Mr. D earned.

5
1 5 1 0
R...x
1 5 3
1 5 1 1
x.R.v
1 1 5
1 5 1
1 5 1 1
x.R.v
1 1 1
1 5 5
3 5 1 4
>L#R>
.###.
<.x.>
3 3 100
1 1 3
1 5 1
3 1 0
3 5 0
3 5 1 5
.v<..
R.>.>
.>..x
3 5 100
1 2 999
1 3 999
2 3 1
2 5 3
3 2 999

3
4
0
99
97

For the second case, you can rotate (1, 5) then you get -1+5=4 value.

For the last case, the optimal solution is rotating (2, 3) 3 times or rotating (2, 5) 1 time, then you get -1*3+100=97 value.

“红旗杯”第十四届吉林省大学生程序设计竞赛