Ampelmännchen

When two countries unite, each one already has its own version of most everyday things: road signs, pickles, ketchup. If one country simply imposes its version on the other, the result feels less like a union of equals and more like an annexation. Many East Germans saw the German unification that way, and it took them years to identify with the new country. A union that holds takes pieces from both sides.

Sometimes both sides agree that one country's version is better. Everyone liked the East German Ampelmännchen, the little walking figure on the pedestrian traffic signal. The hard case is when each side prefers its own version. Then the two sides trade: "we care a lot about our pickles, so let us keep ours, but your ketchup is almost as good as ours, so we will take yours."

You are given a list of contentious items. For each item you know how much each of the two countries likes each of the two versions, and you know how many people live in each country. Every person feels exactly the like value that their own country reports for the version that was chosen. For each item you pick exactly one of the two versions. Maximize the total happiness summed over all people and all items.

Concretely, if the West's version of an item is chosen, that item adds $W \cdot L_{w,w} + E \cdot L_{e,w}$ to the total. If the East's version is chosen, it adds $W \cdot L_{w,e} + E \cdot L_{e,e}$.

The first line contains $K \ge 1$, the number of data sets in the file. $K$ data sets follow.

The first line of a data set contains three integers $n$, $W$, $E$. $0 \le n \le 1000$ is the number of contentious items, and $0 \le W, E \le 10000$ are the numbers of people living in the West and in the East.

Then come $n$ lines, each with four integers $L_{w,w}$, $L_{w,e}$, $L_{e,w}$, $L_{e,e}$, all between 0 and 100. In order they are how much the West likes its own version, how much the West likes the East's version, how much the East likes the West's version, and how much the East likes its own version.

For each data set, print Data Set x: on a line by itself, where $x$ is the number of the data set counting from 1. On the next line print the maximum total happiness reachable by choosing exactly one version of every item. Print a blank line after each data set.