Sunday, March 18, 2012

   We could assume nothing, when top 25 hackers of the world are meeting together in such a place. And there will be something big which will lead to a blasting security threat surely. And it will be widely useful for a Online Service Provider such Facebook. And thats why the company announced their 'Hacker Cup' two years back. The 2nd Season of this tight competition is now under progress and the Final Competition will be held on Company's office at Menlo Park consisting 25 bright hackers On 17/03/2012 Afternoon (US Time)


   Registration of the event was started on Last January and judges have selected 25 Hackers from a huge list of 8000 Submissions to Hacker Cup Final Competition. The hackers are not invited at the office for just time pass or allowing the company to find the security threats of future for free. Facebook will reward $5,000 USD and title as world champion to the top hacker, $2,000 for second place, $1,000 for third, and $100 for fourth through 25th. Awesome t-shirts for the top 100 hackers coming out of the second online round.

 Google's Famous Web Browser, Google Chrome had also intended a hacking competition by rewarding the winners 1 Million US Bucks who Successfully Hacks Google Chrome. Those programmes are very useful for a Company like Facebook more than Chrome since Facebook is a widely growing Social Network and they are including more features like Timeline to their services. As mentioned before, such competitions could help Online Service Providers to know how Stronger are today's hacker is and to intent security systems to resist that Security Threat and save the service. 


 There is needless to say that the problems given in this tight competition is tight than the usual tight when it is by a famous Internet Service Provider. Following one is a sample problem featured in Last Year's Facebook "Hacker Cup". You may have a look at it if you are a Hacker Or in a way to become a Hacker. 


"  You’re throwing a party for your friends, but since your friends may not all know each other, you’re afraid a few of them may not enjoy your party. So to avoid this situation, you decide that you’ll also invite some friends of your friends. But who should you invite to throw a great party?

  Luckily, you are in possession of data about all the friendships of your friends and their friends. In graph theory terminology, you have a subset G of the social graph, whose vertices correspond to your friends and their friends (excluding yourself), and edges in this graph denote mutual friendships. Furthermore, you have managed to obtain exact estimates of how much food each person in G will consume during the party if he were to be invited.

 You want to choose a set of guests from G. This set of guests should include all your friends, and the subgraph of G formed by the guests must be connected. You believe that this will ensure that all of your friends will enjoy your party since any two of them will have something to talk about…

 In order to save money, you want to pick the set of guests so that the total amount of food needed is as small as possible. If there are several ways of doing this, you prefer one with the fewest number of guests.

The people/vertices in your subset G of the social graph are numbered from 0 to N – 1. Also, for convenience your friends are numbered from 0 to F – 1, where F is the number of your friends that you want to invite. You may also assume that G is connected. Note again that you are not yourself represented in G.

Input
The first line of the input consists of a single number T, the number of test cases. Each test case starts with a line containing three integers N, the number of nodes in G, F, the number of friends, and M, the number of edges in G. This is followed by M lines each containing two integers. The ith of these lines will contain two distinct integers u and v which indicates a mutual friendship between person u and person v. After this follows a single line containing N space-separated integers with the ith representing the amount of food consumed by person i.

Output
Output T lines, with the answer to each test case on a single line by itself. Each line should contain two numbers, the first being the minimum total quantity of food consumed at a party satisfying the given criteria and the second the minimum number of people you can have at such a party.

Constraints
T = 50
1 ≤ F ≤ 11
F ≤ N-1
2 ≤ N ≤ 250
N-1 ≤ M ≤ N * (N – 1) / 2
G is connected, and contains no self-loops or duplicate edges.
For each person, the amount of food consumed is an integer between 0 and 1000, both inclusive. "