Problem A
Best Buy

Steam Logo

Steam is digital video game distribution service that is highly popular among PC gamers. You and your group of friends are trying to find a game to play together and everyone is only willing to play the game if it is on Steam. Each of your friends has a list of games they currently own and an amount of money in their steam wallet which they can use to buy a game. Steam also allows players to gift games to other players, and your friends are willing to buy each other a game as long as everyone can play it together. Steam does not allow players to transfer funds from wallet to wallet, so each player gifting a game must be able to afford the game in its entirety. Each game has a name and an associated price and each player’s steam account has a list of the games they own and an integer amount of money in their wallet. Each person in your friend group is willing to buy as many copies of a game as it takes to allow everyone to play together. Given a group of friends’ steam accounts, find the game that costs your friend group the least net amount of money while still allowing everyone to play the game.

Input

The first line of input contains an integer, $2 \leq M \leq 10^5$, that identifies the number of games being considered. The second line contains an integer, $2 \leq N \leq 10^3$, the number of friends in your friend group. The next $M$ lines list the name and price of each game, separated by a space. Each name consists of up to $30$ uppercase or lowercase English letters. The price of each game is an integer between $1$ and $1\, 000$, inclusive.

The following $N$ lines each describe each friend in your group. Each of the lines start with a integer, which is the amount of money in this friend’s wallet, followed by a space separated list of names which are the games in the friend’s library. Each game is listed at most once. All listed names correspond to an entry in the earlier list of games.

Output

Output the name of the game that should be bought and the total amount of money that needs to be spent to buy it, separated by a space. It is guaranteed that there is at most one game that is the cheapest to purchase overall while ensuring each friend has a copy. If there is no game that all players can play with their existing funds, then output “no games found”.

4
3
RocketLeague 15
Dota 8
Apex 20
Valorant 25
0 RocketLeague Dota
15 Apex Valorant
10 RocketLeague

RocketLeague 15

5
4
A 20
B 10
C 15
D 25
E 30
5 A B D
0 C D
15 E
0 D B

no games found