In the beginning of December, parliamentary elections were held in our country. Croatia is divided in 10 election regions. From each region, 14 parliamentary representatives are elected. Each of the voters is voting for one of the few parties. After voting, the representatives are elected using the D'Hondt (D"Ont) method.
By this method, first we select parties which gathered at least of the votes. Number of votes of each of the selected parties is then divided by every number from to . In this way we assign rational numbers - let's call them 'scores' - to each of the parties.
First of the representatives in a region is chosen from a party with the largest score. Second representative is selected from a party with the second largest score. The third... This procedure continues until all of the places are elected. Remark: 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 number of votes each party gained, determines how many politicians were elected as region representatives from each party. Some parties have gained negligible number of votes and will not be in the input - that is the reason that the total number of voters might not be equal to the sum of list votes in the input.
Input Specification
First line of input contains a positive integer , total number of voters in the region.
Second line of input contains a positive integer , number of parties we are considering.
Next lines contain two positive integers divided by a single space: party identifier (capital letter of English alphabet) and a positive integer , number of votes gained by that party.
Output Specification
Output is consisted of number of lines equal to the number of parties which had at least of the votes. For each of these parties, print a party identifier and a number of parliamentary representatives elected from that party. Lines should be sorted by identifiers, alphabetically.
Scoring
In of the test cases, every party in the input will have at least of the votes.
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
Comments
Since the original data were wrong, the affected case has been updated, and all submissions were rejudged.