## PRIPYAT - Pripyat

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_{1}), B = 2 (N_{2}) and so on up to T = 20 (N_{20}).

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.

Added by: | him0727 |

Date: | 2018-04-26 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own problem |