#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
ll c;
set<pair<ll,int> >s,ps;
set<pair<ll,int> >dl;
ll dy=0;
ll t[200001],d[200001];
vector<pair<ll,ll> >sex[200001];

pair<ll,ll>a[200001];
ll b[200001];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> c;
	if(c<=n){
		for(int i=1; i<=n ;i++){
			ll t,d;cin >> t >> d;
			b[i]=(t+d-1)/d;
		}
		sort(b+1,b+n+1);
		ll ans=b[n];
		ll s=0;
		for(int i=1; i<=n ;i++) s+=b[i];
		ans=max(ans,(s+c-1)/c);
		cout << ans-1 << '\n';
		return 0;
	}
	ll ans=0;
	ll ct=0;
	for(int i=1; i<=n ;i++){
		cin >> t[i] >> d[i];
		t[i]=t[i]-d[i]+1;
		sex[i].push_back({d[i],(t[i]-1)/d[i]});
		if((t[i]-1)%d[i]>0) sex[i].push_back({(t[i]-1)%d[i],1});
		sex[i].push_back({1,1});
		s.insert({d[i],i});
		ans+=t[i];
	}
	if(ans<=c){
		cout << "0\n";
		return 0;
	}
	while(s.size()>c){
		ps.insert(*s.begin());
		s.erase(s.begin());
	}
	for(auto c:s){
		int x=c.se;
		dy+=sex[x][0].fi;
		dl.insert({ct+sex[x][0].se,x});
	}
	while(true){
		ll nt=dl.begin()->fi;
		if(ans-(nt-ct)*dy<=c){
			ll res=ct+(ans-c+dy-1)/dy;
			cout << res << '\n';
			return 0;
		}
		ans-=(nt-ct)*dy;
		ct=nt;
		int x=dl.begin()->se;
		int lv=(x-1)/n;
		x-=lv*n;
		dl.erase(dl.begin());
		dy-=sex[x][lv].fi;
		s.erase({sex[x][lv].fi,x+lv*n});
		if(sex[x].size()>lv+1){
			ps.insert({sex[x][lv+1].fi,x+(lv+1)*n});
		}
		if(!ps.empty()){
			auto it=ps.end();--it;
			int x=it->se;ps.erase(it);
			int lv=(x-1)/n;
			x-=lv*n;
			dy+=sex[x][lv].fi;
			s.insert({sex[x][lv].fi,x+lv*n});
			dl.insert({ct+sex[x][lv].se,x+lv*n});
		}
	}
}