P7743 [COCI 2011/2012 #3] D’HONDT

In early December, a certain country holds a parliamentary election. The country is divided into ten constituencies, and each constituency elects $14$ members of parliament. Each voter votes for one of a small number of parties. After voting, the constituency representatives are determined using the D'Hondt allocation method.

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.

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 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.

**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](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T2 D'HONDT_**. Following the original testdata configuration, the full score is $80$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5