Pokemon Identification System

There are many kinds of pokemon. A credential authority is building image processing equipment that identifies them. The unit of the equipment is an agent. An agent is a device with a camera and a dedicated algorithm, and it recognizes exactly one feature, such as having wings or having a tail. One agent type has already been designed for every feature the authority considers important.

The algorithms are not perfect. They miss a feature for some orientations and movement states of a pokemon. They never produce a false positive: an agent either recognizes its feature correctly or returns false. When several agents of the same type analyse one pokemon, the events in which they miss the feature are statistically independent. Deploying several agents of a type therefore raises the reliability for that feature, and the reliability of the whole system follows from those numbers. An identification succeeds only when every agent type reports at least one successful recognition.

If one agent for feature $f$ has reliability $r_f$ and you deploy $k$ agents of that type, the probability of recognizing the feature is $1 - (1 - r_f)^k$. The reliability of the whole system is the product of these probabilities over all $F$ features.

You are given a budget $B$, the number of features $F$, and for each feature the price $c_f$ of one agent and its reliability $r_f$. Find a deployment that maximizes the overall reliability. At least one agent of each type must be deployed, and money may be left unspent.

The input holds a sequence of problems.

The first line of each problem has the budget $B$ and the number of features $F$. ($0 < B \le 10000$, $0 < F \le 30$)

Each of the next $F$ lines has the price $c_f$ of one agent for that feature and its reliability $r_f$. $c_f$ is a positive integer and $r_f$ is a real number with $0 \le r_f \le 1$. The budget is always enough to buy one agent of every type, so the sum of the $c_f$ is at most $B$.

The last line has two zeros. Do not process that line.

For each problem, print one line with the cost of an optimal system and its overall reliability, separated by a space.

Round the reliability and print exactly four digits after the decimal point. A reliability of $0.648$ prints as 0.6480.

If several deployments reach the maximum reliability, print the smallest cost among them. The test data is chosen so that the fourth decimal digit is not a borderline rounding case and so that the optimal cost does not depend on double precision rounding error.

Take three features (wings, tail, legs) and a budget of $105$. The prices are $30$, $15$ and $20$, and the reliabilities are $0.9$, $0.8$ and $0.5$.

The best deployment has one agent of the first type and two of each of the others, for a cost of $30 \times 1 + 15 \times 2 + 20 \times 2 = 100$. The chance of missing the first feature is $1 - 0.9 = 0.1$, for the second it is $(1 - 0.8)^2 = 0.04$, and for the third it is $(1 - 0.5)^2 = 0.25$. The per feature recognition probabilities are then $0.9$, $0.96$ and $0.75$, so the overall reliability is $0.9 \times 0.96 \times 0.75 = 0.648$.