分数: 100 点
问题陈述
林戈王国国会正在对一项法案进行投票。
N 成员出席,并且 i第一个成员 (1 ≤ i ≤ N) 有 w_i 白选票和 b_i 蓝色选票。每位成员 i 将把所有 w_i 如果他/她赞成该法案,请将白色选票放入方框中,并将所有 如果他/她不赞成该法案,则将 b_i 蓝色选票放入方框中。不允许进行任何其他操作。例如,会员不得放弃投票,或仅将部分白选票或部分蓝选票投入箱内。
所有成员投票后,如果至少 P 框中的选票为白色的百分比为白色,该法案通过;如果小于 P % 的选票是白人,该法案被拒绝。
要使该法案获得通过,至少必须有多少议员赞成?
约束
- 1 ≤ N ≤ 10^5
- 1 ≤ P ≤ 100
- 1 ≤ w_i ≤ 10^9
- 1 ≤ b_i ≤ 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P w_1 b_1 w_2 b_2 : w_N b_N
输出
打印支持通过该法案所需的最少成员人数。
示例输入 1
4 75 1 1 1 1 1 1 1 1
示例输出 1
3
这是一次“正常”投票,四名成员中每人都有一张白票和一张蓝票。为了使该法案获得通过,至少 75 百分之四,即至少三人必须赞成。
示例输入 2
4 75 1 1 1 1 1 1 100 1
示例输出 2
1
成员投“赞成”票 100 仅白票就足以通过该法案。
示例输入 3
5 60 6 3 5 9 3 4 7 8 4 7
示例输出 3
3