410456: GYM104023 A Dunai
Description
Lope the Bear often watches game events. He has a special skill: Dunai, also known as poisoned milk. Every time he predicts the outcome of a game by wishing the team that he believes will win good luck, the outcome often turns out to be the opposite. Recently, a tournament called Daota 2 The International is about to start. It's time for Lope to show his Dunai skill again.
In the game Daota 2, each team has five players corresponding to five positions, numbered from $$$1$$$ to $$$5$$$. Daota 2 The International has been held for $$$n$$$ editions. To better Dunai, Lope looks up the champion team of each edition, including the names and positions of the five players. In addition, he inquires about the $$$m$$$ players involved in the upcoming tournament including their names and positions, without knowing exactly how the teams will be formed. What is known is that for every player who has won a championship, his position in the team never changes.
Lope wants to predict how these $$$m$$$ players will be teamed up in a way that satisfies the following conditions:
- Each player is assigned to at most one team (possibly not assigned).
- The team consists of five different positions, with exactly one player for each position.
- Each team includes at least one player who has won a championship.
Lope wants to know the maximum number of teams that can be formed.
InputThe first line contains an integer $$$n$$$ ($$$1 \le n \le 100$$$), indicating the number of editions that the tournament has been held for.
Each of the following $$$n$$$ lines contains five strings separated by spaces, indicating the name of five players in the champion team, corresponding to positions $$$1$$$ to $$$5$$$ respectively.
The next line contains an integer $$$m$$$ ($$$1 \le m \le 1000$$$), indicating the number of players involved in the upcoming tournament.
Each of the following $$$m$$$ lines contains a string and an integer between $$$1$$$ and $$$5$$$, indicating the name and position of a player. It is guaranteed that the names of the players are all distinct, and for every player who has won a championship, his position in the team never changes.
It is guaranteed that the string representing each player's name consists of only English letters and digital numbers, and the length of the string does not exceed $$$20$$$.
OutputOutput an integer indicating the maximum number of teams that can be formed.
ExamplesInput1 Kanon Keke Chisato Sumire Ren 9 Kanon 1 Keke 2 Chisato 3 Sumire 4 Ren 5 Kinako 1 Mei 2 Shiki 3 Natsumi 4Output
1Input
11 skiter Nine 33 Saksa Sneyking Yatoro TORONTOTOKYO Collapse Mira Miposhka ana Topson Ceb JerAx N0tail ana Topson Ceb JerAx N0tail MATUMBAMAN Miracle MinDContRoL GH KuroKy shadow bLink Faithbian iceice y Fear SumaiL UNiVeRsE Aui2000 ppd Hao Mu xiao8 Banana SanSheng Loda s4 AdmiralBulldog EGM Akke Zhou Ferrari430 YYF ChuaN Faith ArtStyle Dendi XBOCT LighTofHeaveN Puppey 100 Ame 1 NothingToSay 2 Faithbian 3 XinQ 4 y 5 Yuragi 1 bzm 2 ATF 3 Taiga 4 Misha 5 Yatoro 1 TORONTOTOKYO 2 Collapse 3 Mira 4 Miposhka 5 K1 1 ChrisLuck 2 Wisper 3 Gojira 4 Stinger 5 Monet 1 Ori 2 Xxs 3 BoBoKa 4 SiameseC 5 Pakazs 1 DarkMago 2 Sacred 3 Matthew 4 Pandaboo 5 JaCkky 1 Yopaj 2 Fbz 3 TIMS 4 skem 5 Timado 1 Bryle 2 SabeRLight 3 MoonMeander 4 DuBu 5 skiter 1 Nine 2 33 3 Saksa 4 Sneyking 5 dyrachyo 1 BOOM 2 Ace 3 tOfu 4 Seleri 5 Arteezy 1 Abed 2 Nightfall 3 Cr1t 4 Fly 5 Raven 1 Armel 2 Jabz 3 DJ 4 Jaunuel 5 YawaR 1 Quinn 2 LESLAO 3 MSS 4 Fata 5 Lumiere 1 4nalog 2 Vitaly 3 Thiolicor 4 Gardick 5 Pure 1 Stormstormer 2 Tobi 3 Kataomi 4 Fishman 5 Daxak 1 Larl 2 Noticed 3 RodjER 4 SoNNeikO 5 Ghost 1 Somnus 2 Chalice 3 kaka 4 xNova 5 23savage 1 Mikoto 2 kpii 3 Q 4 Hyde 5 Crystallis 1 Nisha 2 Resolut1on 3 Zayac 4 Puppey 5 MATUMBAMAN 1 miCKe 2 zai 3 Boxi 4 iNSaNiA 5Output
14