Provident Housewife

Kotoko, a housewife, was enthusiastic about keeping food costs down during this recession. Be sure to check the newspaper advertisement every morning. Make a good list of what to buy and the cheapest-selling shops, and go shopping by riding a bicycle in a combat style called apron sandals while walking through the shops.

So, as a husband, you decided to create a housekeeping book program with your favorite programming in order to help Kotoko even a little. The program inputs the name and price (yen) of the items sold to each supermarket, the items that Kotoko needs, and outputs the minimum amount to collect all the items.

Kotoko has to leave the house, collect the necessary items, and return home. Therefore, you who care about Kotoko decided to add a function to report the distance of the route with the shorter distance, considering that there are multiple shopping routes with the same minimum amount. Therefore, the program also inputs information on the road connecting the supermarket and the house.

Let the number of supers be n, and each super is assigned a number from 1 to n. Furthermore, Kotoko's house is number 0. Road information is given by these number pairs and their distances (integers).

Input

Multiple datasets are given as input. The format of each dataset is as follows:

n (number of supermarkets: integer) k1 name1 value1 name2 value2 ... namek1 valuek1 (number of item types in the first supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) k2 name1 value1 name2 value2 ... namek2 valuek2 (number of item types in the second supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) .. .. kn name1 value1 name2 value2 ... namekn valuekn (number of item types in the nth supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) q (Number of items required: Integer) name1 (Name of the first required item: string) name2 (name of the second required item: string) .. .. nameq (name of the qth required item: string) m (number of roads: integer) s1 t1 d1 (Information on the first road: Blank-separated integers) s2 t2 d2 (Second road information: space-separated integer) .. .. sm tm dm (mth road information: blank-separated integer)

si ti di indicates that the sith supermarket (or house) and the tith supermarket (or house) can move back and forth in both directions, and the distance is di.

You will be given a way to get to all the supermarkets from your house (via the supermarket).

n is less than or equal to 10 and q is less than or equal to 15. ki is 100 or less, the string of the item name does not exceed 20 characters, and the price of the item does not exceed 10000. Also, the length of the road does not exceed 1000.

When n is 0, it is the end of input.

Output

For each dataset, separate the minimum amount and distance with a single space and output on one line. However, if you cannot collect all the necessary items, output "impossible".

Example

Input

3 3 apple 100 banana 200 egg 300 3 apple 150 banana 100 cola 200 3 apple 100 banana 150 cola 200 3 apple banana cola 5 0 2 4 0 1 3 0 3 3 1 2 3 2 3 5 3 3 apple 100 banana 200 egg 300 3 apple 150 banana 100 cola 200 3 apple 100 banana 150 cola 200 4 apple banana cola jump 5 0 2 4 0 1 3 0 3 3 1 2 3 2 3 5 0

Output

400 10 impossible

inputFormat

inputs the name and price (yen) of the items sold to each supermarket, the items that Kotoko needs, and

outputFormat

outputs the minimum amount to collect all the items.

Kotoko has to leave the house, collect the necessary items, and return home. Therefore, you who care about Kotoko decided to add a function to report the distance of the route with the shorter distance, considering that there are multiple shopping routes with the same minimum amount. Therefore, the program also inputs information on the road connecting the supermarket and the house.

Let the number of supers be n, and each super is assigned a number from 1 to n. Furthermore, Kotoko's house is number 0. Road information is given by these number pairs and their distances (integers).

Input

Multiple datasets are given as input. The format of each dataset is as follows:

n (number of supermarkets: integer) k1 name1 value1 name2 value2 ... namek1 valuek1 (number of item types in the first supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) k2 name1 value1 name2 value2 ... namek2 valuek2 (number of item types in the second supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) .. .. kn name1 value1 name2 value2 ... namekn valuekn (number of item types in the nth supermarket, first item name and price, second item name and price ,,,: integer and string blanks Separation) q (Number of items required: Integer) name1 (Name of the first required item: string) name2 (name of the second required item: string) .. .. nameq (name of the qth required item: string) m (number of roads: integer) s1 t1 d1 (Information on the first road: Blank-separated integers) s2 t2 d2 (Second road information: space-separated integer) .. .. sm tm dm (mth road information: blank-separated integer)

si ti di indicates that the sith supermarket (or house) and the tith supermarket (or house) can move back and forth in both directions, and the distance is di.

You will be given a way to get to all the supermarkets from your house (via the supermarket).

n is less than or equal to 10 and q is less than or equal to 15. ki is 100 or less, the string of the item name does not exceed 20 characters, and the price of the item does not exceed 10000. Also, the length of the road does not exceed 1000.

When n is 0, it is the end of input.

Output

For each dataset, separate the minimum amount and distance with a single space and output on one line. However, if you cannot collect all the necessary items, output "impossible".

Example

Input

3 3 apple 100 banana 200 egg 300 3 apple 150 banana 100 cola 200 3 apple 100 banana 150 cola 200 3 apple banana cola 5 0 2 4 0 1 3 0 3 3 1 2 3 2 3 5 3 3 apple 100 banana 200 egg 300 3 apple 150 banana 100 cola 200 3 apple 100 banana 150 cola 200 4 apple banana cola jump 5 0 2 4 0 1 3 0 3 3 1 2 3 2 3 5 0

Output

400 10 impossible

样例

3
3 apple 100 banana 200 egg 300
3 apple 150 banana 100 cola 200
3 apple 100 banana 150 cola 200
3
apple
banana
cola
5
0 2 4
0 1 3
0 3 3
1 2 3
2 3 5
3
3 apple 100 banana 200 egg 300
3 apple 150 banana 100 cola 200
3 apple 100 banana 150 cola 200
4
apple
banana
cola
jump
5
0 2 4
0 1 3
0 3 3
1 2 3
2 3 5
0

400 10
impossible

</p>