← 返回题目列表

AtCoder · relay2_e

E. 白色和蓝色

中文机器翻译题面 查看原题

分数: 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