#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


struct MinimumCostFlow {
	typedef int Index; typedef int Flow; typedef int Cost;
	static const Flow InfCapacity = INF; static const Cost InfCost = INF;
	struct Edge {
		Index to; Index rev;
		Flow capacity; Cost cost;
	};
	vector<vector<Edge> > g;
	void init(Index n) { g.assign(n, vector<Edge>()); }
	void add(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
		Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; e.cost = cost, f.cost = -cost;
		g[i].push_back(e); g[j].push_back(f);
		g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
	}
	void addB(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
		add(i, j, capacity, cost);
		add(j, i, capacity, cost);
	}
	pair<Cost,Flow> minimumCostFlow(Index s, Index t, Flow f = InfCapacity, bool useSPFA = false) {
		int n = g.size();
		vector<Cost> dist(n); vector<Index> prev(n); vector<Index> prevEdge(n);
		pair<Cost,Flow> total = make_pair(0, 0);
		vector<Cost> potential(n);
		while(f > 0) {
			fill(dist.begin(), dist.end(), InfCost);
			if(useSPFA || total.second == 0) {
				deque<Index> q;
				q.push_back(s); dist[s] = 0; vector<bool> inqueue(n);
				while(!q.empty()) {
					Index i = q.front(); q.pop_front(); inqueue[i] = false;
					for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
						const Edge &e = g[i][ei]; Index j = e.to; Cost d = dist[i] + e.cost;
						if(e.capacity > 0 && d < dist[j]) {
							if(!inqueue[j]) {
								inqueue[j] = true;
								q.push_back(j);
							}
							dist[j] = d; prev[j] = i; prevEdge[j] = ei;
						}
					}
				}
			}else {
				vector<bool> vis(n);
				priority_queue<pair<Cost,Index> > q;
				q.push(make_pair(-0, s)); dist[s] = 0;
				while(!q.empty()) {
					Index i = q.top().second; q.pop();
					if(vis[i]) continue;
					vis[i] = true;
					for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
						const Edge &e = g[i][ei];
						if(e.capacity <= 0) continue;
						Index j = e.to; Cost d = dist[i] + e.cost + potential[i] - potential[j];
						if(dist[j] > d) {
							dist[j] = d; prev[j] = i; prevEdge[j] = ei;
							q.push(make_pair(-d, j));
						}
					}
				}
			}
			if(dist[t] == InfCost) break;
			if(!useSPFA) for(Index i = 0; i < n; i ++) potential[i] += dist[i];
			
			Flow d = f; Cost distt = 0;
			for(Index v = t; v != s; ) {
				Index u = prev[v]; const Edge &e = g[u][prevEdge[v]];
				d = min(d, e.capacity); distt += e.cost; v = u;
			}
			if(distt >= 0) break;
			f -= d; total.first += d * distt; total.second += d;
			for(Index v = t; v != s; v = prev[v]) {
				Edge &e = g[prev[v]][prevEdge[v]];
				e.capacity -= d; g[e.to][e.rev].capacity += d;
			}
		}
		return total;
	}
};
int main() {
	int N;
	scanf("%d", &N);
	const int A = 26, B = 10;
	vector<vector<bool> > doors(A, vector<bool>(B, false));
	rep(i, N) {
		char a[2]; int b;
		scanf("%s%d", a, &b);
		doors[*a - 'A'][b] = true;
	}
	int M;
	scanf("%d", &M);
	vector<vector<int> > keys(A, vector<int>(B, INF));
	rep(i, M) {
		char c[2]; int d, e;
		scanf("%s%d%d", c, &d, &e);
		amin(keys[*c - 'A'][d], e);
	}
	int ans = INF;
	MinimumCostFlow mcf;
	rep(digits, 1 << B) {
		int alphas = 0;
		rep(j, A) rep(k, B) if((~digits >> k & 1) && doors[j][k])
			alphas |= 1 << j;
		vi alphasCosts(A, INF), digitsCosts(B, INF);
		rep(j, A) {
			if(alphas >> j & 1) {
				rep(k, B)
					amin(alphasCosts[j], keys[j][k]);
			}else {
				alphasCosts[j] = 0;
			}
		}
		rep(k, B) {
			if(digits >> k & 1) {
				rep(j, A)
					amin(digitsCosts[k], keys[j][k]);
			}else {
				digitsCosts[k] = 0;
			}
		}
		if(count(all(alphasCosts), INF) != 0 || count(all(digitsCosts), INF) != 0)
			continue;
		int src = A + B, dst = src + 1;
		mcf.init(dst + 1);
		rep(j, A)
			mcf.add(src, j, 1);
		rep(j, A) rep(k, B) if(keys[j][k] != INF)
			mcf.add(j, A + k, 1, keys[j][k] - alphasCosts[j] - digitsCosts[k]);
		rep(k, B)
			mcf.add(A + k, dst, 1);
		int minMatch = mcf.minimumCostFlow(src, dst).first;
		int cost = 0;
		cost += accumulate(all(alphasCosts), 0);
		cost += accumulate(all(digitsCosts), 0);
		cost += minMatch;
		amin(ans, cost);
	}
	if(ans == INF)
		puts("-1");
	else
		printf("%d\n", ans);
	return 0;
}
### Prompt

Please formulate 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 <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


struct MinimumCostFlow {
	typedef int Index; typedef int Flow; typedef int Cost;
	static const Flow InfCapacity = INF; static const Cost InfCost = INF;
	struct Edge {
		Index to; Index rev;
		Flow capacity; Cost cost;
	};
	vector<vector<Edge> > g;
	void init(Index n) { g.assign(n, vector<Edge>()); }
	void add(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
		Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; e.cost = cost, f.cost = -cost;
		g[i].push_back(e); g[j].push_back(f);
		g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
	}
	void addB(Index i, Index j, Flow capacity = InfCapacity, Cost cost = Cost()) {
		add(i, j, capacity, cost);
		add(j, i, capacity, cost);
	}
	pair<Cost,Flow> minimumCostFlow(Index s, Index t, Flow f = InfCapacity, bool useSPFA = false) {
		int n = g.size();
		vector<Cost> dist(n); vector<Index> prev(n); vector<Index> prevEdge(n);
		pair<Cost,Flow> total = make_pair(0, 0);
		vector<Cost> potential(n);
		while(f > 0) {
			fill(dist.begin(), dist.end(), InfCost);
			if(useSPFA || total.second == 0) {
				deque<Index> q;
				q.push_back(s); dist[s] = 0; vector<bool> inqueue(n);
				while(!q.empty()) {
					Index i = q.front(); q.pop_front(); inqueue[i] = false;
					for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
						const Edge &e = g[i][ei]; Index j = e.to; Cost d = dist[i] + e.cost;
						if(e.capacity > 0 && d < dist[j]) {
							if(!inqueue[j]) {
								inqueue[j] = true;
								q.push_back(j);
							}
							dist[j] = d; prev[j] = i; prevEdge[j] = ei;
						}
					}
				}
			}else {
				vector<bool> vis(n);
				priority_queue<pair<Cost,Index> > q;
				q.push(make_pair(-0, s)); dist[s] = 0;
				while(!q.empty()) {
					Index i = q.top().second; q.pop();
					if(vis[i]) continue;
					vis[i] = true;
					for(Index ei = 0; ei < (Index)g[i].size(); ei ++) {
						const Edge &e = g[i][ei];
						if(e.capacity <= 0) continue;
						Index j = e.to; Cost d = dist[i] + e.cost + potential[i] - potential[j];
						if(dist[j] > d) {
							dist[j] = d; prev[j] = i; prevEdge[j] = ei;
							q.push(make_pair(-d, j));
						}
					}
				}
			}
			if(dist[t] == InfCost) break;
			if(!useSPFA) for(Index i = 0; i < n; i ++) potential[i] += dist[i];
			
			Flow d = f; Cost distt = 0;
			for(Index v = t; v != s; ) {
				Index u = prev[v]; const Edge &e = g[u][prevEdge[v]];
				d = min(d, e.capacity); distt += e.cost; v = u;
			}
			if(distt >= 0) break;
			f -= d; total.first += d * distt; total.second += d;
			for(Index v = t; v != s; v = prev[v]) {
				Edge &e = g[prev[v]][prevEdge[v]];
				e.capacity -= d; g[e.to][e.rev].capacity += d;
			}
		}
		return total;
	}
};
int main() {
	int N;
	scanf("%d", &N);
	const int A = 26, B = 10;
	vector<vector<bool> > doors(A, vector<bool>(B, false));
	rep(i, N) {
		char a[2]; int b;
		scanf("%s%d", a, &b);
		doors[*a - 'A'][b] = true;
	}
	int M;
	scanf("%d", &M);
	vector<vector<int> > keys(A, vector<int>(B, INF));
	rep(i, M) {
		char c[2]; int d, e;
		scanf("%s%d%d", c, &d, &e);
		amin(keys[*c - 'A'][d], e);
	}
	int ans = INF;
	MinimumCostFlow mcf;
	rep(digits, 1 << B) {
		int alphas = 0;
		rep(j, A) rep(k, B) if((~digits >> k & 1) && doors[j][k])
			alphas |= 1 << j;
		vi alphasCosts(A, INF), digitsCosts(B, INF);
		rep(j, A) {
			if(alphas >> j & 1) {
				rep(k, B)
					amin(alphasCosts[j], keys[j][k]);
			}else {
				alphasCosts[j] = 0;
			}
		}
		rep(k, B) {
			if(digits >> k & 1) {
				rep(j, A)
					amin(digitsCosts[k], keys[j][k]);
			}else {
				digitsCosts[k] = 0;
			}
		}
		if(count(all(alphasCosts), INF) != 0 || count(all(digitsCosts), INF) != 0)
			continue;
		int src = A + B, dst = src + 1;
		mcf.init(dst + 1);
		rep(j, A)
			mcf.add(src, j, 1);
		rep(j, A) rep(k, B) if(keys[j][k] != INF)
			mcf.add(j, A + k, 1, keys[j][k] - alphasCosts[j] - digitsCosts[k]);
		rep(k, B)
			mcf.add(A + k, dst, 1);
		int minMatch = mcf.minimumCostFlow(src, dst).first;
		int cost = 0;
		cost += accumulate(all(alphasCosts), 0);
		cost += accumulate(all(digitsCosts), 0);
		cost += minMatch;
		amin(ans, cost);
	}
	if(ans == INF)
		puts("-1");
	else
		printf("%d\n", ans);
	return 0;
}
```