Code Festival Team Relay (Parallel)

E - White and Blue


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

4 人の議員がそれぞれ白票 1 枚と青票 1 枚を持っている「普通」の投票です。法案の可決には、4 人のうち 75 パーセント、すなわち 3 人以上の賛成が必要です。


入力例 2

4 75
1 1
1 1
1 1
100 1

出力例 2

1

100 枚の白票を持っている議員 1 人の賛成で法案が可決されます。


入力例 3

5 60
6 3
5 9
3 4
7 8
4 7

出力例 3

3

Score : 100 points

Problem Statement

Ringo Kingdom Congress is voting on a bill.

N members are present, and the i-th member (1 ≤ i ≤ N) has w_i white ballots and b_i blue ballots. Each member i will put all the w_i white ballots into the box if he/she is in favor of the bill, and put all the b_i blue ballots into the box if he/she is not in favor of the bill. No other action is allowed. For example, a member must not forfeit voting, or put only a part of his/her white ballots or a part of his/her blue ballots into the box.

After all the members vote, if at least P percent of the ballots in the box is white, the bill is passed; if less than P percent of the ballots is white, the bill is rejected.

In order for the bill to pass, at least how many members must be in favor of it?

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ P ≤ 100
  • 1 ≤ w_i ≤ 10^9
  • 1 ≤ b_i ≤ 10^9
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N P
w_1 b_1
w_2 b_2
:
w_N b_N

Output

Print the minimum number of members in favor of the bill required for passage.


Sample Input 1

4 75
1 1
1 1
1 1
1 1

Sample Output 1

3

This is a "normal" vote, where each of the four members has one white ballot and one blue ballot. For the bill to pass, at least 75 percent of the four, that is, at least three must be in favor of it.


Sample Input 2

4 75
1 1
1 1
1 1
100 1

Sample Output 2

1

The "yes" vote of the member with 100 white ballots alone is enough to pass the bill.


Sample Input 3

5 60
6 3
5 9
3 4
7 8
4 7

Sample Output 3

3

Submit提出する