DHONDT#9429
In early December, parliamentary elections were held in our country. Azerbaijan is divided into electoral regions, and from each region, parliamentary representatives are elected. Each voter votes for one of several parties. After the voting, representatives are selected using the D'Hondt method.
According to this method, we first select parties that have received at least of the votes. The number of votes of each such party is then divided by each integer from to . This way, we assign rational numbers (let's call them "scores") to each party.
The first of the representatives in a region is chosen from the party with the largest score, the second representative from the party with the second largest score, and so on. This procedure continues until all seats are filled. Note: There will always be a unique way to elect the representatives, i.e., no two scores will be equal.
Write a program that, given the total number of voters and the number of votes each party received, determines how many representatives from each party were elected as region representatives. Some parties have received a negligible number of votes and are not included in the input — therefore, the total number of voters may not equal the sum of the listed votes in the input.
The first line contains a positive integer (1 \le X \le 2\ 500\ 000), the total number of voters in the region.The second line contains a non-negative integer (0 \le N \le 10), the number of parties considered. Each of the next lines contains a party identifier (an uppercase English letter) and a non-negative integer (0 \le G \le 250\ 000), the number of votes received by that party.
Print as many lines as there are parties that received at least of the votes. For each of these parties, print the party identifier and the number of parliamentary representatives elected from that party. The lines should be sorted alphabetically by party identifier.
Example 1
Example 2
Example 3