[vb_gallery id=404774]

More than 6,000 hopefuls from around the world entered Facebook’s programming challenge, the Hacker Cup, in January. Three months later, just 25 finalists went head-to-head in a three-hour battle for supremacy today at Facebook’s new Menlo Park campus.

The winner will have his name (all 25 finalists are male) inscribed on a 50-pound trophy, a sort of pixelated-looking two-dimensional brass fist with the work “HACK” blazoned it, which is set on top of a cube of concrete.

**Update:** After three hours of competition, Facebook has announced the winners of the 2012 Hacker Cup:

- 1st place: Roman Andreev from Russia, completed one problem correctly in 1 hr 4 min
- 2nd place: Tomek Czajka from the US, completed one problem correctly in 1 hr 5 min
- 3rd place: Tiancheng Lou from China, completed one problem correctly in 1 hr 44 min

There’s a $5,000 prize for the first-place winner, but most of the reward will be the glory of being named, publicly, as one of the world’s top coders. Plus, of course, there’s the thrill of going up against a roomful of world-class programmers.

“They’re here because they love competing in these things,” said David Alves, a software engineer at Facebook and one of the event organizers.

All but one are from overseas. Countries represented in the finals include Russia, Germany, Ukraine, Poland, China, South Korea, Taiwan, Japan, and the U.S. After making it through three successively more challenging qualification rounds, the 25 finalists are here at Facebook’s expense for a couple of days of visiting, bowling, and three intense hours of coding.

Facebook’s Hacker Cup is not the only such coding competition. Many of the coders here also compete in TopCoder contests and Google Code Jam, as well as in coding contests in their home countries. That’s one reason Alves surmises that certain regions, such as Eastern Europe and Asia, produce more successful code contestants: They are more used to competitions like these. Plus, he adds, their countries have excellent science and math education.

The Hacker Cup works like this: Each coder is given three difficult programming problems and three hours to solve them. In the first round, the problems are easy: For instance, figure out the maximum size font you can use for a sign of a given size and specified text. By the time the challengers reach the final round, the problems are mind-bendingly tough. (See below for a sample problem from last year’s competition.) Alves expected that only one or two contestants would complete all three problems and that only about half of them would even complete one — which is how things turned out last year at Facebook’s first Hacker Cup competition.

Contestants can use whatever programming language and development environment they want, though 70 percent choose C++, Alves said. (A minority use Java, and one or two might use C#.) After completing the program, the contestant can test it out, then submit it to the judges. The program has six minutes to run, and if it produces the correct result, it passes.

Judges determine the winners based on the accuracy of the results their programs produce, followed by the speed with which the coder came up with the solution.

It’s a challenge that tests the computer science skills of all the contestants but also demands a level of intuition and out-of-the-box thinking.

“Usually the straightforward way of solving the problem won’t be anywhere near fast enough,” Alves said.

Physically speaking, the Hacker Cup is not much to look at: A bunch of young men staring intensely at their oversized monitors for three hours straight. The room was so quiet that the clicking of my camera’s shutter was the loudest noise to be heard. After an hour, the Hacker Cup webpage displayed on the wall showed that three contestants had completed one problem apiece. The silence with which that news appeared belied the underlying intensity.

Contestants are not supposed to collaborate or communicate with anyone on the outside, though they do have Internet access and can, for example, look things up on Wikipedia. But Alves is not too worried about anyone outsourcing their problem sets.

“Who are they going to outsource to?” Alves said. “The people in this room are the best qualified to solve these problems.”

### Sample problem

Wondering what it’s like to compete in the Hacker Cup? Take a look at this problem from last year’s competion. Remember, this is just one of three problems, and you’d have just three hours to create a program to solve all three.

Party Time

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.

*Photos: Dylan Tweney/VentureBeat, except as noted.*