Pripyat is an abandoned city in Ukraine. On April 27, 1986, the whole population of Pripyat was evacuated because of the Chernobyl nuclear power plant accident.

Today (April 26) is the 32nd anniversary of the Chernobyl nuclear disaster, and Duck plans to visit Chernobyl to know more about this disaster. He has a list of N must-visit places in Pripyat, with its excitation level EXC, time required to visit VT and radiation level RL. Of course, sometimes it is impossible to visit all places because of limited visiting time and the danger of radiation. Given his maximum of available time to visit MVT and tolerance to radiation level TRL, can you help him to select some places to visit so that the total EXC is maximized and the VT and RL are less than or equal to the given limit. 

Based on your finding, given a matrix MX showing some barriers that are not allowed to pass through, Duck's hotel location and all must-visited places' location, determine the minimum distance to be moved to visit all the selected places starting from his hotel location. Duck can only move to adjacent cells that share one edge horizontally or vertically, and he can only visit the selected place once. That is, he cannot pass through the selected place twice or more. Also, he cannot pass through the unselected places.

Input

The first line is the number of test cases T. (1 <= T <= 25)

For each test case, it starts with two integers: number of must-visit places N (1 <= N <= 20) and his maximum of available time to visit MVT (1 <= MVT <= 100) , and one real number: tolerance to radiation level TRL. (0.01 <= TRL <= 10)

Following N lines, each showing ith place's information, consisting of two integers: excitation level EXC (1 <= EXC <= 100) and time required to vistit VT (1 <= VT <= 100), and one real number: radiation level RL. (0.01 <= RL <= 10)

After that, a line consists of two integers: number of rows of the matrix R, and number of colunms of the matrix C. (1 <= R, C <= 50)

Next R lines, each has C characters, representing the map of Pripyat MX. '+' means hotel location, '.' means available cells Duck can walk, '#' means barriers Duck cannot pass through, and N consecutive upper letters counting from A corresponding to ith place, eg. A = 1 (N₁), B = 2 (N₂) and so on up to T = 20 (N₂₀).

It is guranteed that R * C >= N + 1, and all real numbers are with at most two digits after the decimal point.

Output

One integer indicating the minimum distance to be moved to visit all the selected places starting from his hotel location. If there are multiple combinations, choose the first in alphabetical order.

If no places are selected, output '0'; if it is impossible to visit all selected places, output '-1' (without quotes).

Example

Input:
2
5 8 0.8
3 1 0.04
9 9 0.1
4 2 0.12
10 5 0.2
7 2 0.02
8 10
.B...#....
...#.+.#.C
..A.....#.
..##.##.##
....#..E..
#.........
#.....##..
#..#..D...
5 18 1.6
8 6 0.04
9 9 0.1
4 5 0.12
10 5 0.2
3 1 0.02
8 10
.B...#....
...#.+.#..
........#.
..########
....#...DE
#.......##
#.##..###A
...#..C...
Output:
17
-1

Explanation

In test case 1, A, D, E are selected and the minimum distance to visit all of them from '+' is 17.

In test case 2, A, C, D, E are selected. But D blocks E and C blocks A, it is impossible to visit all selected places once only. Duck has to visit C twice or D twice.