Description

In one constituency, there are $x$ voters, and $n$ parties participate in the election. Using the D'Hondt allocation method, we first select the parties whose votes account for at least $5\%$ of the total number of voters. Then, for a given party, we divide its number of votes by $1,2,\dots,14$, and treat the $14$ resulting real numbers as that party’s scores. Next, we choose the first representative from the party with the highest score, the second representative from the party with the second-highest score, and so on. Note that in this problem, we assume the way representatives are chosen is always unique, i.e., all scores are different.

Now, write a program that, given the total number of voters and the number of votes each party receives, outputs, among all parties whose votes account for at least $5\%$ of the total number of voters, how many representatives each party can elect.

Input Format

The input contains $n+2$ lines.

The first line contains an integer $x$, the number of voters.
The second line contains an integer $n$, the number of parties participating in the election.
The next $n$ lines each contain an uppercase letter and an integer $g$, representing the party identifier and the number of votes the party received.

Output Format

Output several lines. Each line contains an uppercase letter and an integer, representing the identifier of a party whose votes account for at least $5\%$ of the total number of voters, and the number of representatives it can elect.

All parties whose votes account for at least $5\%$ of the total number of voters should be output in ascending alphabetical order by their identifiers.

235217
3
A 107382
C 18059
B 43265

A 9
B 4
C 1

245143
4
F 14845
A 104516
B 52652
C 14161

A 8
B 4
C 1
F 1

206278
5
D 44687
A 68188
C 7008
B 48377
G 9665

A 6
B 4
D 4

Hint

Constraints

For $30\%$ of the testdata, it is guaranteed that all parties in the input have votes accounting for at least $5\%$ of the total number of voters.
For all testdata, $1\leqslant x\leqslant 2.5\times 10^6$, $0\leqslant n\leqslant 10$, $1\leqslant g\leqslant 2.5\times 10^5$.

Source

This problem is from COCI 2011-2012 CONTEST 3 T2 D'HONDT. Following the original testdata configuration, the full score is $80$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5