Com molts altres, Bambino ha passat l'últim mes practicant el distanciament social. No perquè hi hagi COVID, sinó perque comprar en Desembre és terrible i a Bambino no li agrada la gent. Com a part dels seus esforços, ha començat a comprar totalment en línia. Ha descobert que les compres en línia ofereixen molts avantatges. En particular, pots mirar fàcilment molts llocs web diferents per trobar el millor preu per a un article.

No obstant això, altres també han començat a comprar en línia, la qual cosa significa que les botigues s'estan quedant sense existències. Com a resultat, Bambino sovint ha de fer comandes a múltiples llocs web per aconseguir tots els articles que vol.

Bambino té diversos articles que ha de comprar. Pots ajudar a Bambino a determinar la quantitat mínima de diners que necessita gastar per comprar tots els articles?

Entrada

La primera línia comença amb un únic enter T (1 ≤ T ≤ 10), el nombre de casos de prova. Segueixen T casos de prova.

Cada cas de prova comença amb un enter N (1 ≤ N ≤ 100), el nombre de botigues. Segueixen N descripcions de botigues.

Cada descripció de botiga comença amb un enter M (1 ≤ M ≤ 100), el nombre d'articles diferents venuts a cada botiga. Les següents M línies contenen cadascuna una cadena en minúscules S i dos enters P,Q (1 ≤ P,Q ≤ 100): el nom d'un article, el seu preu i la quantitat que la botiga té en estoc. El nom de cada article serà únic i contindrà com a màxim 50 caràcters.

La següent línia conté un enter K (1 ≤ K ≤ 100), el nombre d'articles diferents que Bambino vol comprar. Les següents K línies contenen cadascuna un nom d'article S i un enter D (1 ≤ D ≤ 100), la quantitat d'aquest article que Bambino vol comprar. El nom de cada article apareixerà com a màxim una vegada.

Es garanteix que, a diferència del món real, la quantitat total de cada article disponible a les botigues és més gran o igual a la quantitat que Bambino vol comprar.

Sortida

Per a cada cas de prova, imprimeix un únic enter: la quantitat mínima que Bambino necessita gastar per comprar tots els articles que vol.

Exemple d'Entrada

1
2
2
toiletpaper 1 50
catnip 2 25
1
toiletpaper 100 1
2
toiletpaper 51
catnip 10

Exemple de Sortida

170