프로그램 명: coci_dhondt
제한시간: 1 초

12 월 초에 , 국회의원 선거가 있었다. 크로아티아는 10 개의 지역구로 나누어져 있다. 각 지역에는 14 명의 대표가 선출된다. 유권자들은 여러 정당 중 한 정당에 투표를 할 수 있다.

선거 후 , 대표자들은 D'Hondt 방법으로 선출 된다.

이 방법은 ,

이 과정이 14 번 반복된다. 참조: 대표를 뽑을 유일한 방법이 존재한다고 하자. 즉 같은 스코어를 가진 정당이 없다.

유권자 수와 각 정당별 득표가 주어질 때 각 정당별 대표자 수를 구하는 프로그램을 작성하라.

득표수가 작은 정당은 입력으로 주어지지 않을 수 있다. - 이는 전체 득표자 수와 입력으로 주어지는 정당별 득표수와 같지 않을 수도 있다는 것이다.

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 5% of the votes. Number of votes of each of the selected parties is then divided by every number from 1 to 14. In this way we assign 14 rational numbers - let’s call them ‘scores’ - to each of the parties. First of the 14 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 14 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.

입력

First line of input contains a positive integer X (1 ≤ X ≤ 2 500 000), total number of voters in the region. Second line of input contains a positive integer N (0 ≤ N ≤ 10), number of parties we are considering. Next N lines contain two positive integers divided by a single space: party identifier (capital letter of English alphabet) and a positive integer G (0 ≤ G ≤ 250 000), number of votes gained by that party.

출력

Output is consisted of number of lines equal to the number of parties which had at least 5% 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, alphabeticaly.

입출력 예

input

235217
3
A 107382
C 18059
B 43265

output

A 9
B 4
C 1

input

245143
4
F 14845
A 104516
B 52652
C 14161

output

A 8
B 4
C 1
F 1

input

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

output

A 6
B 4
D 4

출처:coci
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]