Problem Background

In early December, a certain country holds parliamentary elections. The country is divided into ten constituencies, each electing 14 representatives to the parliament. Each voter votes for one of the minority parties. After voting, the constituency representatives are elected using the D'Hondt allocation method.

Problem Description

In a particular constituency, there are $x$ voters and $n$ parties participating in the parliamentary election. Using the D'Hondt allocation method, we first select the parties that have received at least 5% of the total votes. Then, for each party's vote count, we divide it by $1, 2, \dots, 14$, and use these 14 resulting real numbers as the party's scores. We then select 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 method of electing representatives is always unique, meaning all scores are distinct.

Now, please write a program that, given the total number of voters and the number of votes each party received, determines the number of representatives each party can elect, among those parties that received at least 5% of the total votes.

Input Format

The input consists of $n+2$ lines.

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

Output Format

Output several lines, each containing a capital letter and an integer, representing the identifier of a party that received at least 5% of the total votes and the number of representatives it can elect.

The parties that received at least 5% of the total votes should be sorted in ascending order by their identifier in the alphabet.

Sample Input and Output

Sample Input #1

235217
3
A 107382
C 18059
B 43265

Sample Output #1

A 9
B 4
C 1

Sample Input #2

245143
4
F 14845
A 104516
B 52652
C 14161

Sample Output #2

A 8
B 4
C 1
F 1

Sample Input #3

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

Sample Output #3

A 6
B 4
D 4

Notes

[Data Range]

For 30% of the test cases, it is guaranteed that all parties have received at least 5% of the total votes.
For all test cases, $1 \leqslant x \leqslant 2.5 \times 10^6$, $0 \leqslant n \leqslant 10$, $1 \leqslant g \leqslant 2.5 \times 10^5$.

[Problem Source]

This problem is from COCI 2011-2012 CONTEST 3 T2 D'HONDT, configured with the original data. Full score is 80 points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分