Pro-Test Voting

Old Bob Test is running for Mayor of the Hamlet of Kerning. Kerning is divided into several precincts (numbered 0, 1, 2, ...). After extensive polling, Bob knows the current percentage of voters in each precinct who plan to vote for him. He would like to raise these percentages everywhere, but his funds are limited.

Based on past results, the effect of spending in a precinct follows the equation

$$F_p = I_p + \left(\frac{M}{10.1 + M}\right)\Delta$$

where $I_p$ is the current percentage of pro-Test voters, $\Delta$ is the maximum possible increase in this percentage, $M$ is the amount of money spent in the precinct as a non-negative integer number of dollars (multiples of $1), and $F_p$ is the resulting expected percentage. Determine how Bob should spend his money to maximize the total number of votes he receives.

The first line of each test case contains two integers $m$ and $n$: the amount of money Bob has to spend (in dollars) and the number of precincts. Both are at most $100$. The next $n$ lines each have the form $N\ I_p\ \Delta$, all positive integers, describing a precinct: $N$ is the precinct's population (less than $10000$), and $I_p$ and $\Delta$ are as described above. The first of these lines is precinct 0, the next is precinct 1, and so on.

A line containing 0 0 follows the last test case.

To find the number of pro-Test voters in a precinct, first compute $F_p$ with the formula above using floating-point arithmetic, then multiply that percentage by the population $N$ (that is, $F_p \times N / 100$) and round to the nearest integer, rounding halves up.

For each test case, output two lines. The first line contains the case number followed by the maximum number of votes Bob can obtain through optimal spending. The second line lists, for every precinct, how much money Bob should spend there, each entry written as precinct:money and separated by a single blank.

Case X: votes
0:money0 1:money1 ...

If more than one way of spending the money yields the maximum number of votes, output the one that spends the most on precinct 0; if several tie on precinct 0, take the one that spends the most on precinct 1, and so on.