#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];
bool check(ll mid){
	ll need=0;
	for(int i=1; i<=n ;i++){
		if(t[i]<=d[i]*mid);
		else{
			ll fun=t[i]-d[i]*(mid+1);
			need+=1+max(fun,0LL);
		}
	}
	if(need<=c) return true;
	else return false;
}
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;
	}
	for(int i=1; i<=n ;i++){
		cin >> t[i] >> d[i];
	}
	ll l=0,r=1e9;
	while(l!=r){
		ll mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << '\n';
}