In the city Crimiville, there are N notorious gangster heads. They’ve plagued the city for a very long time, but they are too sly to get caught. However, the polices are not stupid. CRPD (CRimiville Police Department) has also N special agents to monitor every slight movement of the N gangster heads. Each special agent i monitors a set of the head Si constantly; he knows very well about every single gangster head that is in his watch. (Note that,
without saying, Si and Sj could overlap; that is, different agent could be monitoring some same gangster head).
The gangster heads are aware of this (They are not stupid, either! Crimiville is a clever city!!), so they also have their way to respond. Some of the criminal heads (possibly all, one, or any set) may group together and form a “malicious group” (MG) to carry out some of their evil plans. When such a group is formed, all the police aware of the existence of this group will form a “crisis management panel” (CMP) to monitor the malicious group together. A police is aware of the “malicious group” if he originally monitors some criminal head that participates the group.
The final showdown comes when the criminal heads in a malicious group actually put their evil plan to light — when they actually perfrom some crime. In this case, whether the police (the CMP) will be able to stop the malicious group is determined by a simple rule:
Each police has an ability measure Ai , and each criminal has a danger measure Di. In the case of (3) above, the estimated danger for the incident is simply:
Estimated Danger = ∑ Di − ∑ Aj, for each i∈MG and j∈CMP.
Now, given all these values, and information of which agents watch which criminal heads, the CRPD want to know whether the city is in immediate crisis (is it possible the evil could destroy the city in some cases)? If so, they will need to ask for reinforcement of agent resources. If not, please help CRPD estimate what is the greatest danger they could encounter in a single incident carried out by some malicious group? (In case every case is not danger or the estimated danger is non-positive, just output zero)
The first line of the input file contains an integer indicating the number of test cases to follow.
Each test case starts with a line containing a single integer, N. Then follows N lines describing the monitoring status of each agent, each with the following format: A line starts with an integer Ki , the number of criminal heads agent i monitors. Right after that comes Ki integers being the IDs of criminal heads monitored by agent i (0-indexed). Finally the last two lines each contain N numbers, being the ability value of agent 0, 1, 2, ..., N − 1, and then the dangerous measure of criminal 0, 1, 2, ..., N − 1, respectively.
For each test case, if the city is currently in crisis of being burnt down, print “need reinforcement.”; otherwise print just one integer, indicating the maximum danger possibly enountered by the CRPD. Note that this value
should always be non-negative.
2 4 1 0 3 0 2 3 1 0 2 1 3 1 1 1 1 2 2 2 2 6 2 1 2 1 0 1 1 2 3 4 2 3 5 2 4 5 1 2 1 11 20 20 1 2 2 38 1 1
need reinforcement. 2
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|