#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=2e5+10;

ll c,n,t[maxn],d[maxn];

using int128=__int128_t;
int cnt[maxn];
vector<pair<pii,int>>cand;
bool check(ll mid){

    for(int i=1;i<=n;i++)cnt[i]=0;

    ll total=min(((int128)mid+1)*min(n,c),(int128)1e18);

    ll sum=0;
    ll cpc=c;
    int i=-1;
    while(++i<cand.size() && total>0){

        int x=cand[i].ss;

        ll d=min(min(total,(ll)cand[i].ff.ss), (ll)mid+1-cnt[x] );

        cnt[x]+=d;
        total-=d;

        sum+=(cand[i].ff.ss-d)*(ll)cand[i].ff.ff;
    }

    for(;i<cand.size();i++){
        sum+=cand[i].ff.ss*(ll)cand[i].ff.ff;
    }

    for(int i=1;i<=n;i++)if(cnt[i]==mid+1)cpc--;
    cpc=min(cpc,total);

    return sum<=cpc;
}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%lld %lld",&n,&c);

    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&t[i],&d[i]);

        cand.pb({{d[i],t[i]/d[i]},i});
        if(t[i]%d[i])cand.pb({{t[i]%d[i],1},i});
    }
    sort(cand.begin(),cand.end());
    reverse(cand.begin(),cand.end());

    //check(249);
    //return 0;

    ll l=0;
    ll r=2e15;
    ll sr,ret=0;
    while(l<=r){
        sr=(l+r)/2;
        if(check(sr)){
            r=sr-1;
            ret=sr;
        }
        else l=sr+1;
    }
    printf("%lld\n",ret);

    return 0;
}