Problem D
Delicious Bubble Tea

Bubble Tea is now one of the most popular drink in Vietnam. Nowadays, walking down on the street, you can find a bubble tea shop everywhere. A huge number of bubble tea brands have arrived: Bobapop, Chago, DingTea, GongCha, Mr.GoodTea, RoyalTea, ToCoToCo,… Bubble tea attracts students not only as a tasty drink, but also with various kinds of extra topping: alo vera, chocolate flan, coconut jelly, egg pudding, fruity pearl,…Ok, I will stop writing this statement here as I must get some bubble tea immediately. It is so so so addictive.

\includegraphics[width=0.4\textwidth ]{bubbletea.jpg}
Bubble tea
\includegraphics[width=0.4\textwidth ]{toppings.png}

After teaching a philosophy class to Vietnamese students preparing for International Philosophy Olympiad, PVH invites his students to enjoy a cup of bubble tea. The tea shop sells $N$ kinds of tea and $M$ kinds of topping. Every kind of tea or topping has its own price. For each student, PVH will buy him a cup of tea with exactly one kind of topping. The cost of a cup equals to the cost of the tea plus the cost of the topping. However, not every kind of topping can be mixed with every kind of tea. For each kind of tea, we know the list of toppings can be mixed with.

Given the amount of money PVH has, he would like to know how many students he can invite to the party, if one student drinks exactly one cup of bubble tea. Remember, he never watches his students drinking bubble tea without drinking anything, so he must buy himself a cup of bubble tea first!


  • The first line contains one integer $N$ - the amount of kinds of tea the shop has.

  • The second line contains $N$ integers - the price of all kinds of tea.

  • The third line contains one integer $M$ - the amount of toppings the shop has.

  • The forth line contains $M$ integers - the price of all kinds of topping.

  • The $i^{th}$ of the next $N$ lines describes the toppings that can be mixed with th $i^{th}$ kind of tea. The line starts with an integer $K$, followed by $K$ integers. All these $K$ integers are in the range $[1, M]$ and pairwise different. Each integer denotes a kind of topping which can be combined with the $i^{th}$ kind of tea.

  • The last line contains one integer $X$ - the amount of money PVH has.


Write the maximum number of students PVH can buy bubble tea for.


The amount of money is between $1$ and $10^9$, inclusive. All other numbers in the input files are between $1$ and $1\, 000$, inclusive.

Sample clarification

In this example, there are three kinds of tea with price 10, 20 and 30; as well as five kinds of topping with price from 1 to 5.

The cheapest combination of tea and topping is the first kind of tea with the forth kind of topping, with a total cost of 14. Note that, while combining the first kind of tea with the first kind of topping gives lower price (11), it is not allowed since the first kind of tea is only combinable with toppings of kind 4 and 5. (See the $5^{th}$ line of the input).

Hence, with the amount of money of 42, PVH can buy three cups of tea, one for him and two more for his students!

Sample Input 1 Sample Output 1
10 20 30
1 2 3 4 5
2 4 5
3 1 2 3
5 1 2 3 4 5

Please log in to submit a solution to this problem

Log in