A — 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.

Bubble tea

Toppings

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 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 that it 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!

Input Specification

The first line contains one integer N — the number of kinds of tea the shop has.

The second line contains N integers — the price of each kind of tea.

The third line contains one integer M — the number of toppings the shop has.

The forth line contains M integers — the price of each kind of topping.

The ith of the next N lines describes the toppings that can be mixed with the ith 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 ith kind of tea.

The last line contains one integer X — the amount of money PVH has.

Output Specification

Output a single line containing the maximum number of students PVH can buy bubble tea for.

Constraints

The amount of money is between 1 and 10⁹, inclusive. All other numbers in the input are between 1 and 1000, inclusive.

Sample Input

1. 3
2. 10 20 30
3. 5
4. 1 2 3 4 5
5. 2 4 5
6. 3 1 2 3
7. 5 1 2 3 4 5
8. 42

download as text file

Output for Sample Input

1. 2

download as text file

Clarification of the Sample

In this example, there are three kinds of tea with prices 10, 20, and 30; as well as five kinds of topping with prices 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 5th 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!

Original Problem

ACM ICPC 2017 Asia HCMC Vietnam National Programming Contest