#include <bits/stdc++.h>
using namespace std;

#define rep2(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) rep2(i,0,n)
#define sz(x) ((int)(x).size())
#define MAX_V 40
int INF = 1e9;
const int MM = 1234567;
typedef pair<int,int> P;

struct edge{ int to, cap,cost,rev; };

int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];

int dbg = 0;

void add_edge(int from,int to,int cap,int cost){
	if(dbg){
		cout<<"ae "<<from<<" "<<to<<" "<<cap<<" "<<cost<<endl;
	}
	G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
	G[to].push_back({from,0,-cost,(int)G[from].size()-1});
}
long min_cost_flow(int s,int t,int f){
	long res = 0;
	fill(h,h+V,INF);
	h[s] = 0;
	while(true){
		int flag = 0;
		//cout << "--" << endl;
		for(int v = 0 ; v < V ; v++){
			for(int i = 0 ; i < G[v].size(); i++){
				edge &e = G[v][i];
				if( e.cap > 0 && h[e.to] > h[v] + e.cost){
					h[e.to] = h[v] + e.cost;
					flag = true;
					//cout << "==" << endl;
				}
			}
		}
		if(!flag) break;
	}
	if(dbg){rep(i,V)cout<<i<<": "<<h[i]<<" "<<endl;}
	while( f > 0 ){
		fill(dist,dist+V,INF);
		priority_queue<P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s] = 0;
		que.push(P(0,s));
		while( !que.empty() ){
			P p = que.top(); que.pop();
			int v = p.second;
			if( dist[v] < p.first ) 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 + h[v] - h[e.to] ){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to],e.to));
				}
			} 
		}
		if(dbg){rep(i,V)if(dist[i]<INF)cout<<i<<": "<<dist[i]<<" "<<endl;}

		if( dist[t] == INF){
			if(dbg)cout<<"A!"<<endl;
			return res; // !!!
		}
		for(int v = 0 ; v < V ; v++) h[v] += dist[v];
		
		int d = f;
		for(int v = t ; v != s ; v = prevv[v]){
			d = min(d,G[prevv[v]][preve[v]].cap);
		}

		if(h[t] >= 0){ // !!!
			if(dbg)cout<<"B!"<<endl;
			return res;
		}

		f -= d;
		res += d * h[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 bsum;


void add_edge2(int from, int to, int cost, int mincap, int maxcap){
	if(dbg)cerr<<from<<" "<<to<<" "<<cost<<" "<<mincap<<" "<<maxcap<<endl;
	bsum += mincap;
	add_edge(from, to, maxcap - mincap, cost);
	add_edge(from, to, mincap, cost-MM);
}

int N, M;
int cond[11][27];
int card[11][27];

int main(){
	cin>>N;
	rep(i,N){
		//cin>>a[i]>>b[i];
		char a; int b;
		cin>>a>>b;
		cond[b][a-'A'] = 1;
	}
	/*rep(i,10)rep(j,26){
		cout<<cond[i][j]<<(j==25?"\n":" ");
	}*/
	rep(i,10)rep(j,26) card[i][j] = INF;
	cin>>M;
	rep(i,M){
		char c; int d; int e;
		cin>>c>>d>>e;
		card[d][c-'A'] = min(card[d][c-'A'], e);
	}
	/*rep(i,10)rep(j,26){
		cout<<cond[i][j]<<(j==25?"\n":" ");
	}*/
	/*rep(i,10)rep(j,26){
		cout<<card[i][j]<<(j==25?"\n":" ");
	}*/
	int ans = INF;
	rep(mask,1<<10){ // buy
		//if(mask == (1<<3)) dbg = 1; else dbg = 0;

		V = 38;
		bsum = 0;
		rep(i,V)G[i].clear();
		int s = 36, t = 37;
		rep(i,10)if(mask>>i&1){
			add_edge2(s, 0+i, 0, 1, 36);
		}
		int survive[26] = {};
		rep(i,10)rep(j,26){
			if(cond[i][j] && !(mask>>i&1)){
				survive[j] = 1;
			}
		}
		if(dbg){
			rep(j,26)cout<<survive[j];cout<<endl;
		}
		rep(j,26)if(survive[j]){
			add_edge2(10+j, t, 0, 1, 36);
		}
		rep(i,10)rep(j,26)if(card[i][j] < INF){
			if(!(mask>>i&1)) continue;
			if(survive[j]){
				add_edge2(0+i, 10+j, card[i][j], 0, 1);
			}else{
				add_edge2(0+i, t, card[i][j], 0, 1);
			}
		}

		int res = min_cost_flow(s, t, 36);
		if(dbg)cout<<res<<" "<<bsum<<" "<<res+MM*bsum<<endl;
		res += MM * bsum;
		ans = min(ans, res);
	}
	if(ans >= MM)cout<<-1<<endl;
	else cout<<ans<<endl;
}
### Prompt

Your challenge is to write a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define rep2(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) rep2(i,0,n)
#define sz(x) ((int)(x).size())
#define MAX_V 40
int INF = 1e9;
const int MM = 1234567;
typedef pair<int,int> P;

struct edge{ int to, cap,cost,rev; };

int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];

int dbg = 0;

void add_edge(int from,int to,int cap,int cost){
	if(dbg){
		cout<<"ae "<<from<<" "<<to<<" "<<cap<<" "<<cost<<endl;
	}
	G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
	G[to].push_back({from,0,-cost,(int)G[from].size()-1});
}
long min_cost_flow(int s,int t,int f){
	long res = 0;
	fill(h,h+V,INF);
	h[s] = 0;
	while(true){
		int flag = 0;
		//cout << "--" << endl;
		for(int v = 0 ; v < V ; v++){
			for(int i = 0 ; i < G[v].size(); i++){
				edge &e = G[v][i];
				if( e.cap > 0 && h[e.to] > h[v] + e.cost){
					h[e.to] = h[v] + e.cost;
					flag = true;
					//cout << "==" << endl;
				}
			}
		}
		if(!flag) break;
	}
	if(dbg){rep(i,V)cout<<i<<": "<<h[i]<<" "<<endl;}
	while( f > 0 ){
		fill(dist,dist+V,INF);
		priority_queue<P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s] = 0;
		que.push(P(0,s));
		while( !que.empty() ){
			P p = que.top(); que.pop();
			int v = p.second;
			if( dist[v] < p.first ) 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 + h[v] - h[e.to] ){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to],e.to));
				}
			} 
		}
		if(dbg){rep(i,V)if(dist[i]<INF)cout<<i<<": "<<dist[i]<<" "<<endl;}

		if( dist[t] == INF){
			if(dbg)cout<<"A!"<<endl;
			return res; // !!!
		}
		for(int v = 0 ; v < V ; v++) h[v] += dist[v];
		
		int d = f;
		for(int v = t ; v != s ; v = prevv[v]){
			d = min(d,G[prevv[v]][preve[v]].cap);
		}

		if(h[t] >= 0){ // !!!
			if(dbg)cout<<"B!"<<endl;
			return res;
		}

		f -= d;
		res += d * h[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 bsum;


void add_edge2(int from, int to, int cost, int mincap, int maxcap){
	if(dbg)cerr<<from<<" "<<to<<" "<<cost<<" "<<mincap<<" "<<maxcap<<endl;
	bsum += mincap;
	add_edge(from, to, maxcap - mincap, cost);
	add_edge(from, to, mincap, cost-MM);
}

int N, M;
int cond[11][27];
int card[11][27];

int main(){
	cin>>N;
	rep(i,N){
		//cin>>a[i]>>b[i];
		char a; int b;
		cin>>a>>b;
		cond[b][a-'A'] = 1;
	}
	/*rep(i,10)rep(j,26){
		cout<<cond[i][j]<<(j==25?"\n":" ");
	}*/
	rep(i,10)rep(j,26) card[i][j] = INF;
	cin>>M;
	rep(i,M){
		char c; int d; int e;
		cin>>c>>d>>e;
		card[d][c-'A'] = min(card[d][c-'A'], e);
	}
	/*rep(i,10)rep(j,26){
		cout<<cond[i][j]<<(j==25?"\n":" ");
	}*/
	/*rep(i,10)rep(j,26){
		cout<<card[i][j]<<(j==25?"\n":" ");
	}*/
	int ans = INF;
	rep(mask,1<<10){ // buy
		//if(mask == (1<<3)) dbg = 1; else dbg = 0;

		V = 38;
		bsum = 0;
		rep(i,V)G[i].clear();
		int s = 36, t = 37;
		rep(i,10)if(mask>>i&1){
			add_edge2(s, 0+i, 0, 1, 36);
		}
		int survive[26] = {};
		rep(i,10)rep(j,26){
			if(cond[i][j] && !(mask>>i&1)){
				survive[j] = 1;
			}
		}
		if(dbg){
			rep(j,26)cout<<survive[j];cout<<endl;
		}
		rep(j,26)if(survive[j]){
			add_edge2(10+j, t, 0, 1, 36);
		}
		rep(i,10)rep(j,26)if(card[i][j] < INF){
			if(!(mask>>i&1)) continue;
			if(survive[j]){
				add_edge2(0+i, 10+j, card[i][j], 0, 1);
			}else{
				add_edge2(0+i, t, card[i][j], 0, 1);
			}
		}

		int res = min_cost_flow(s, t, 36);
		if(dbg)cout<<res<<" "<<bsum<<" "<<res+MM*bsum<<endl;
		res += MM * bsum;
		ans = min(ans, res);
	}
	if(ans >= MM)cout<<-1<<endl;
	else cout<<ans<<endl;
}
```