Orange Bowl

It is late in the Orange Bowl football game, and USC is trailing by 4 points, desperately needing one more touchdown. So the coach reaches for his newest weapon: a play-strategy evaluator written at a programming contest.

Football is complicated, but we simplify it as follows. USC is currently $n$ yards away from the end zone ($1 \le n \le 100$). The coach must choose a sequence of plays to move the ball into the end zone as safely as possible. For each play, the coach may pick from $m$ available plays ($1 \le m \le 1000$). Each play $i$ is described by two numbers: a yard gain $g_i$ (an integer with $1 \le g_i \le 100$) and a success probability $p_i$ (a real number with $0 \le p_i \le 1$). The play succeeds with probability $p_i$; if it succeeds, it moves USC $g_i$ yards closer to the end zone, and if it fails, the ball is turned over and USC loses.

Choose a sequence of plays (repetitions allowed) whose total yard gain is at least $n$ and whose overall success probability is maximized. All plays succeed independently, so the success probability of a sequence is the product of the individual probabilities.

(An aside from the original contest: "Like USC would ever be trailing in a football game.")

The first line contains an integer $K \ge 1$, the number of data sets. Then follow $K$ data sets, each of the following form.

The first line of a data set contains $n$ and $m$. This is followed by $m$ lines; the $i$-th of them contains $g_i$ and $p_i$ for play $i$.

For each data set, first print a line "Data Set x:", where x is the data set's number (starting from 1). Then, on its own line, print the overall success probability of the play sequence most likely to reach the end zone, rounded to two decimals. You do not need to print the actual sequence.