Ice Cream

Some overqualified, underpaid famous computer scientists are heading home after a long day of hard work when they decide to stop for ice cream. They immediately notice that the price per scoop gets cheaper as the order grows: a triple scoop is cheaper per scoop than a double, and a double is cheaper per scoop than a single. But not everyone wants three scoops, so they decide to combine their requests into cost-efficient orders and then split the scoops among themselves. For example, if three people each want a single scoop, they can order one triple scoop and divide it into three single scoops, satisfying everyone at the lowest cost.

The store sells only two flavors: vanilla and chocolate. Everyone uses cups instead of cones, and cups are free and unlimited. Each person requests some number of vanilla scoops and some number of chocolate scoops. There is one complication: if a single purchased unit (a single, double, or triple) contains at least one vanilla scoop and at least one chocolate scoop, the scoops melt into one another and every scoop in that unit becomes contaminated. For instance, a triple with a chocolate scoop on the bottom and two vanilla scoops on top still leaves all three scoops contaminated. People who ordered at least one scoop of each flavor do not mind, since they wanted both anyway, but people who ordered only one flavor will not accept any cross-contamination. What is the lowest total cost that satisfies everyone's requests?

The first line contains the number $K$ of data sets, followed by the $K$ data sets, each of the following form.

The first line of each data set contains four integers $n$, $s$, $d$, and $t$, where $1 \le n \le 100$ is the number of computer scientists and $s$, $d$, and $t$ are the prices in cents of a single, double, and triple scoop, respectively. The prices satisfy $1 \le s < d < t \le 1000$ and $s > \frac{1}{2}d > \frac{1}{3}t$. The next $n$ lines each contain two integers $v$ and $c$: the number of vanilla scoops and the number of chocolate scoops that customer wants, where $0 \le v, c \le 10000$.

For each data set, first print Data Set x: on its own line, where $x$ is the data-set number starting from 1. On the next line, print the minimum total cost in cents so that everyone receives all requested scoops. Print a single blank line between consecutive data sets.