#D7240. Dungeon of Cards
Dungeon of Cards
Dungeon of Cards
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
inputFormat
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
outputFormat
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
样例
4
D 1
D 2
A 3
D 4
4
A 1 7
D 4 5
D 3 6
B 3 36