G: Dungeon of Cards

story

This is a wonderland hydrangea. It is said that gold and silver treasures sleep in the labyrinth of cards located in the remote area of ​​Ajifurai. As soon as the curious Aizu Nyan heard this legend, he decided to take his friend Wi and go on a journey to the Labyrinth of Cards.

The next day, when Aizu Nyan visited Wi's house to plan a trip, Wi seemed to be thinking about something. Apparently well-prepared Wi got important information about the Labyrinth of Cards. That is, there are N doors in the card labyrinth, and you need a card to open each door.

On the way to the card labyrinth, there is a store that sells cards to open the door. Wi seems to be thinking about procuring cards here, but the problem is the budget. Aizu Nyan and Wi are never rich, so if you spend too much money on your card, you may not be able to get enough food along the way.

Fortunately, information on the N doors can be found in the records of those who have challenged the labyrinth so far. If this is the case, it may be possible to calculate how to buy an efficient card. However, it is a little difficult for two people to think about. So Aizu Nyan and Wi decided to ask you, an excellent programmer living in Ajifurai.

problem

There are N doors and M cards. Each door and card has one uppercase alphabet ('A'-'Z') and one digit number ('0'-'9'). When you hold the card over the door, you can open the door if either the alphabet or the number drawn on the card matches that of the door. At this time, the card is not lost, so the same card can be reused many times. In addition, each card has a price.

Based on the information of N doors and M cards, create a program that calculates the minimum amount of money required to buy a card that can open all the doors.

Input format

The input consists of the following format.


N
a_1 b_1
...
a_N b_N
M
c_1 d_1 e_1
...
c_M d_M e_M


The first line gives the integer N, which represents the number of doors. Of the following N lines, the i-th line is given the uppercase alphabet a_i and the one-digit number b_i written on the i-th door.

In the next line, the number of cards M handled in the store is given. Of the following M lines, the jth line gives the uppercase alphabet c_j written on the jth card, the one-digit number d_j, and the price e_j.

The input satisfies the following constraints.

* 1 ≤ N, M ≤ 10 {,} 000
* a_i and c_j are uppercase letters ('A'-'Z')
* b_i and d_j are single digit numbers ('0'-'9') 1 character
* 1 ≤ e_j ≤ 1 {,} 000
* N, M, e_j are all integers



Output format

Print the minimum budget on one line to get all the cards you need to open all the labyrinth doors. If you can't open all the doors no matter how you buy the card, print -1 on one line.

Input example 1


Four
D 1
D 2
A 3
D 4
Four
A 1 7
D 4 5
D 3 6
B 3 3


Output example 1


6

Input example 2


Four
D 1
D 2
A 3
D 4
Four
A 1 7
D 4 5
D 3 10
B 3 3


Output example 2


8

Input example 3


Five
D 1
D 2
A 3
Z 0
D 4
Four
A 1 7
D 4 5
D 3 6
B 3 3


Output example 3


-1





Example

Input

4
D 1
D 2
A 3
D 4
4
A 1 7
D 4 5
D 3 6
B 3 3


Output

6
#include <bits/stdc++.h>
#define MAX_V 40
#define INF 1e5
using namespace std;

/*テヲツ慊?・ツーツ湘ィツイツサテァツ板ィテヲツオツ?テ」ツδッテ」ツδシテ」ツつキテ」ツδ」テ」ツδォテ」ツδ陛」ツδュテ」ツつ、テ」ツδ嘉、ツスツソテァツ板ィ) O(F|V||E|)*/

//ティツセツコテ」ツつ津ィツ。ツィテ」ツ?凖ヲツァツ凝ゥツ??、ツスツ?ティツ。ツ古」ツ?催・ツ?暗」ツ??・ツョツケテゥツ?湘」ツ??」ツつウテ」ツつケテ」ツδ暗」ツ??ゥツ??ィツセツコ)
struct edge{int to, cap,cost,rev;};
int V;                         //テゥツ?づァツつケテヲツ閉ー
vector<edge> G[MAX_V];         //テ」ツつーテ」ツδゥテ」ツδ陛」ツ?ョテゥツ堋」テヲツ篠・テ」ツδェテ」ツつケテ」ツδ暗ィツ。ツィテァツ渉セ
int dist[MAX_V];               //テヲツ慊?ァツ淞ュティツキツ敕ゥツ崢「
int prevv[MAX_V],preve[MAX_V]; //テァツ崢エテ・ツ可催」ツ?ョテゥツ?づァツつケテ」ツ?ィティツセツコ

// fromテ」ツ?凝」ツつ液oテ」ツ?クテ・ツ青妥」ツ?凝」ツ??・ツョツケテゥツ?縦apテ」ツ??」ツつウテ」ツつケテ」ツδ?ostテ」ツ?ョティツセツコテ」ツつ津」ツつーテ」ツδゥテ」ツδ陛」ツ?ォティツソツステ・ツ環?」ツ?凖」ツつ凝」ツ??
void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
  G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}

//sテ」ツ?凝」ツつ液テ」ツ?クテ」ツ?ョテヲツオツ?ゥツ?叔テ」ツ?ョテヲツ慊?・ツーツ湘ィツイツサテァツ板ィテヲツオツ?」ツつ津ヲツアツづ」ツつ?」ツつ?
//テヲツオツ?」ツ?崚」ツ?ェテ」ツ??・ツ?エテ・ツ青?1テ」ツつ津ィツソツ氾」ツ??
int min_cost_flow(int s,int t,int f){
  int res=0;
  while(f>0){
    //テ」ツδ凖」ツδォテ」ツδ榲」ツδウテ」ツδ陛」ツつゥテ」ツδシテ」ツδ嘉ヲツウツ陛」ツ?ォテ」ツつ暗」ツつ?s-tテゥツ鳴禿ヲツ慊?ァツ淞ュティツキツッテ」ツつ津ヲツアツづ」ツつ?」ツつ?
    fill(dist,dist+V,INF);
    dist[s]=0;
    bool update = true;
    while(update){
      update = false;
      for(int v=0; v<V ;v++){
	if(dist[v]==INF) continue;
	for(int i=0; i<G[v].size(); i++){
	  edge &e = G[v][i];
	  if(e.cap > 0 && dist[e.to] > dist[v]+e.cost) {
	    dist[e.to] = dist[v] + e.cost;
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    update = true;
	  }
	}
      }
    }
    if(dist[t]==INF) return -1; //テ」ツ?禿」ツつ古、ツサツ・テ、ツクツ甘ヲツオツ?」ツ?崚」ツ?ェテ」ツ??」ツ??
    
    //sテ「ツ按稚テゥツ鳴禿ァツ淞ュティツキツッテ」ツ?ォテヲツイツソテ」ツ?」テ」ツ?ヲテァツ崢ョテ、ツクツ?ヲツ敖ッテヲツオツ?」ツ??
    int d = f;
    for(int v=t; v!=s; v=prevv[v])d=min(d,G[prevv[v]][preve[v]].cap);
    f -= d;
    res += d*dist[t];
    for(int v=t; v!=s; v=prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int door[26][10],key[26][10];
int mnalpha[26],mnnum[10];

int S = 26+10,T=S+1;
void mkG(int bit){
  for(int i=0;i<MAX_V;i++)G[i].clear();

  V = 26+10+2;
  //0 -> 25 num
  //26 -> 35 alpha
  
  for(int i=0;i<26;i++)add_edge(S,i,1,0);
  for(int i=0;i<10;i++)add_edge(i+26,T,1,0);

  set<int> used;
  for(int i=0;i<26;i++)
    for(int j=0;j<10;j++){
      if((bit>>j&1)||door[i][j]==0)continue;
      used.insert(i);
    }
  
  for(int i=0;i<26;i++){
    if(used.count(i)==0) add_edge(i,T,1,0);
    else add_edge(i,T,1,mnalpha[i]);
    for(int j=0;j<10;j++){
      if(bit>>j&1)add_edge(i,26+j,1,key[i][j]-mnnum[j]);
    }
  }
}

int main(){
  int n,m;
  cin>>n;
  for(int i=0;i<n;i++){
    char ch;
    int num;
    cin>>ch>>num;
    door[ch-'A'][num] = 1;
  }

  for(int i=0;i<26;i++)for(int j=0;j<10;j++)key[i][j]=INF;
  for(int i=0;i<10;i++) mnnum[i]=INF;
  for(int i=0;i<26;i++) mnalpha[i] = INF;
  
  cin>>m;  
  for(int i=0;i<m;i++){
    char ch;
    int num,cost;
    cin>>ch>>num>>cost;
    key[ch-'A'][num] = min(key[ch-'A'][num],cost);
    mnnum[num] = min(cost,mnnum[num]);
    mnalpha[ch-'A']=min(cost,mnalpha[ch-'A']);
  }

  int ans = INF;
  for(int i=0;i<(1<<10);i++){
    mkG(i);
    int cost=0;
    for(int j=0;j<10;j++)if(i>>j&1) cost+=mnnum[j];
    int res = min_cost_flow(S,T,26);
    if(res!=-1)ans=min(ans,cost+res);
  }
  if(ans>=INF) ans=-1;
  cout<<ans<<endl;
  return 0;
}