Woburn Challenge 2017-18 Round 3 - Senior Division

You own a group of ~N~ ~(1 \le N \le 400\,000)~ webpages dedicated solely to the art of dynamic programming. Each page ~i~ includes links to ~K_i~ ~(0 \le K_i < N)~ other distinct pages, the ~j~-th of which is page ~L_{i, j}~ ~(1 \le L_{i, j} \le N)~. The total number of links ~(\sum K_{1 \dots N})~ is at most ~400\,000~. You consider a given page ~b~ to be "accessible" from a given page ~a~ if it's possible to follow a sequence of 0 or more links starting from page ~a~ and ending at page ~b~.

Unfortunately, your pages aren't getting as much traffic as you'd like. It's clear that the most promising way of encouraging more people to come across your pages is to somehow cause them to appear earlier in the search results when someone searches for "dynamic programming" on the internet's most popular search engine.

Each page is assigned an integral "relevancy score" for a given search query such as "dynamic programming", and pages with higher scores then appear earlier in the results for that query. Page ~i~'s initial relevancy score is ~R_i~ ~(1 \le R_i \le 10^9)~. Fortunately, if you donate ~C_i~ ~(1 \le C_i \le 10^4)~ dollars to the search engine company, you can increase page ~i~'s score by ~1~! You can choose to do so ~0~ or more times for any page.

You're not yet sure about how much money you'd like to spend on helping to make your pages "more relevant", so you'll consider a series of ~M~ ~(1 \le M \le 400\,000)~ independent questions. For the ~i~-th question, you'd like to determine the minimum amount of money you'd need to spend in order to make all ~N~ of your pages "accessible" from search results with relevancy scores no smaller than ~Q_i~ ~(1 \le Q_i \le 10^9)~. In other words, after you finish increasing all of the pages' scores as necessary, for each page ~b~ ~(1 \le b \le N)~, there must exist at least one page ~a~ such that page ~a~'s final relevancy score is greater than or equal to ~Q_i~ and page ~b~ is accessible from page ~a~. Note that all ~M~ questions are independent, with changes to pages' scores not carrying over between them.

Subtasks

In test cases worth ~9/38~ of the points, ~N \le 2\,000~, ~\sum K_{1 \dots N} \le 2\,000~, and ~M = 1~.
In test cases worth another ~15/38~ of the points, ~M = 1~.

Input Specification

The first line of input consists of a single integer, ~N~.
~N~ lines follow, the ~i~-th of which consists of three space-separated integers, ~R_i~, ~C_i~, and ~K_i~, followed by ~K_i~ more integers ~L_{i, 1 \dots K_i}~, for ~i = 1 \dots N~.
The next line consists of a single integer, ~M~.
~M~ lines follow, the ~i~-th of which consists of a single integer, ~Q_i~, for ~i = 1 \dots M~.

Output Specification

Output ~M~ lines, the ~i~-th of which should consist of a single real number, the minimum cost (in dollars) required such that all ~N~ pages are accessible from search results with relevancy scores no smaller than ~Q_i~.

Sample Input

5
9 3 1 4
11 1 0
8 2 1 1
4 2 1 3
7 2 1 2
3
10
12
1

Sample Output

9
18
0

Sample Explanation

If page ~1~'s relevancy score is increased to ~10~ (for a cost of ~$3~) and page ~5~'s relevancy score is also increased to ~10~ (for a cost of ~$6~), then all ~5~ pages will be reachable from search results with relevancy scores no smaller than ~10~. Pages ~1~, ~2~, and ~5~ will have sufficiently high relevancy score themselves, and page ~1~ links to page ~4~ which then links to page ~3~. This total cost of ~$9~ is optimal.