问题 1119. -- 选举

1119: 选举

时间限制: 1 Sec  内存限制: 32 MB
提交: 62  解决: 17
[提交][状态][讨论版]

题目描述

某地进行选举,一共要选出 14 位议员。有若干个党派,一张选票只能投给一个党派。现在有

 

X 张选票,已知每个党派获得的选票。有一些党派得到的票数太少,以至于可以忽略不计。现

 

在的选举规则是这样的:首先只考虑获得不少于所有选票数的 5%的党派,将这些党派得到的

 

选票数除以 1~14 的每个数,这样每个党派就将得到 14 个有理数。第一个议员来自于最大的那

 

个数代表的党派,第二个议员来自于第二大的数代表的党派,这样直到 14 个议员都产生。注意:

 

保证一定能够选出 14 个议员,也就是说没有两个有理数是相等的。

 

现在请输出那些产生议员的党派和产生的数量。

输入

第一行包含一个正整数 X(1<=X<=2500000),表示所有的选票。

 

接下来一个整数 N(0<=N<=10),表示我们考虑的党派数量。接下来行,每行一个字符和一

 

个整数,以空格隔开。字符代表党派名称,整数代表该党派获得的选票数量,

 

0<=G<=250000。

 

注意,因为有些党派忽略不计,所以列出的党派获得选票数之和不一定等于选票的总数。

输出

有多少个党派获得不少于 5%的选票,输出就有多少行。

 

输出党派的编号和它产生的议员的数量,用空格隔开。

样例输入

235217
3
A 107382
C 18059
B 43265

样例输出

A 9
B 4
C 1

提示

输出满足题目要求的党派编号按字典顺序输出

来源

[提交][状态]