Problem: 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.

Examples

Input

4 75
1 1
1 1
1 1
1 1


Output

3


Input

4 75
1 1
1 1
1 1
100 1


Output

1


Input

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


Output

3

Solution (in CPP):

Solution:
//start of jonathanirvings' template v3.0.3 (BETA)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <deque>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <time.h>
#include <bitset>
#include <list>
#include <assert.h>
#include <time.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n,p;
pii data[100005];

bool f(pii a,pii b)
{
  return (LL)a.fi * (a.se + b.fi) > (LL)b.fi * (a.fi + b.se);
}

bool g(pii a,pii b)
{
  return a.fi - a.se > b.fi - b.se;
}

bool h(pii a,pii b)
{
  return (LL)a.fi * b.se > (LL)a.se * b.fi;
}

bool s1(pii a,pii b)
{
  if (a.se != b.se) return a.se > b.se;
  return a.fi > b.fi;
}

bool s2(pii a,pii b)
{
  if (a.fi != b.fi) return a.fi > b.fi;
  return a.se > b.se;
}

bool s3(pii a,pii b)
{
  return (LL)a.fi * a.se > (LL)b.fi * b.se;
}

bool s4(pii a,pii b)
{
  return a.fi + a.se > b.fi + b.se;
}

bool s5(pii a,pii b)
{
  return SQR(a.fi) + SQR(a.se) > SQR(b.fi) + SQR(b.se);
}

bool s6(pii a,pii b)
{
  return (LL)(100 - p) * a.fi + (LL)p * a.se > (LL)(100 - p) * b.fi + (LL)p * b.se;
}

int ans1()
{
  sort(ALLA(data,n),f);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans2()
{
  sort(ALLA(data,n),g);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans3()
{
  sort(ALLA(data,n),h);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans4()
{
  sort(ALLA(data,n),s1);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans5()
{
  sort(ALLA(data,n),s2);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans6()
{
  sort(ALLA(data,n),s3);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans7()
{
  sort(ALLA(data,n),s4);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans8()
{
  sort(ALLA(data,n),s5);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int ans9()
{
  sort(ALLA(data,n),s6);
  pair<LL,LL> now = mp(0,0);
  REP(i,n) now.se += data[i].se;
  REP(i,n)
  {
    now.fi += data[i].fi;
    now.se += data[i].fi - data[i].se;
    if (100LL * now.fi >= (LL)p * now.se)
    {
      return i + 1;
    }
  }
  return n;
}

int main()
{
  scanf("%d %d",&n,&p);
  REP(i,n) scanf("%d %d",&data[i].fi,&data[i].se);
  int risan = ans1();
  MIN(risan,ans2());
  MIN(risan,ans3());
  MIN(risan,ans4());
  MIN(risan,ans5());
  MIN(risan,ans6());
  MIN(risan,ans7());
  MIN(risan,ans8());
  MIN(risan,ans9());
  printf("%d\n",risan);
  return 0;
}