407390: GYM102783 C Optimal Trick or Treating

Little Timmy is going trick or treating this year, but has decided that he will only look for his favorite kind of candy: Chuckles bars. Unfortunately, Alice has bought up all of the Chuckles bars in the neighborhood and using them to trade for other candies, so Timmy must find the candies that Alice is looking for and trade them in for Chuckles bars. Alice has posted $$$n$$$ types of trades that she is willing to make, where a trade consists of a type of candy and how many Chuckles bars Alice is willing to give for one piece of that type of candy.

Little Timmy has done extensive research and discovered what candies and amounts each of the $$$h$$$ houses in his neighborhood is going to be giving out. When Little Timmy goes to a particular house, he can take all of the candy that the house is giving out. However, he only has time to visit $$$k$$$ different houses before the night ends. Given the candies that each house gives out and the deals Alice is willing to make, what is the maximum amount of Chuckles bars that Little Timmy can end up getting?

The first line of the input will consist of a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$), which gives the number of deals that Alice is willing to make. The next $$$n$$$ lines of the input will consist of a string $$$s_i$$$ made of only alphanumeric characters ($$$1 \leq |s_i| \leq 15$$$) and an integer $$$v_i$$$ ($$$1 \leq v_i \leq 100$$$), which indicates that Alice is willing to give $$$v_i$$$ Chuckles bars for a single candy with the name $$$s_i$$$. The next line of the input will consist of two integers $$$h$$$ and $$$k$$$ ($$$1 \leq k \leq h \leq 200$$$), which gives the number of houses in Timmy's neighborhood and the number of houses that he can visit. The next lines of the input consist of $$$h$$$ house-descriptions, which consist of a single integer $$$c_i$$$ ($$$1 \leq c_i \leq n$$$) giving the number of types of candies that house $$$i$$$ is giving out, followed by $$$c_i$$$ lines that each consist of one of the $$$n$$$ types of candies that Alice is willing to send and an integer $$$m_j$$$ ($$$1 \leq m_j \leq 100$$$) that gives the number of candies of that type that house $$$i$$$ is giving out.

Output a single integer and new line that gives the maximum number of Chuckles bars that Little Timmy can end up collecting.

3
LactoseyWay 2
Twicks 3
DigDog 5
2 1
2
LactoseyWay 3
Twicks 1
1
DigDog 2

10