#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const ll lim=1e18;
const ll inf=1e18;
const int N=200050;
ll used[N];
int main(){
	int n,c;
	scanf("%i %i",&n,&c);
	vector<array<ll,3>> take;
	ll sum=0;
	for(int i=1;i<=n;i++){
		int t,d;
		scanf("%i %i",&t,&d);
		sum+=t;
		take.pb({d,t/d,i});
		if(t%d!=0){
			take.pb({t%d,1,i});
		}
	}
	sort(take.rbegin(),take.rend());
	ll top=lim,bot=0,ans;
	while(top>=bot){
		ll mid=top+bot>>1;
		for(int i=1;i<=n;i++)used[i]=0;
		ll now=sum;
		ll canUse;
		if(inf/c<mid+1)canUse=inf;
		else canUse=(mid+1)*c;
		for(auto p:take){
			ll can=min({mid+1-used[p[2]],p[1],canUse});
			now-=can*p[0];
			canUse-=can;
			used[p[2]]+=can;
		}
		ll left=c;
		for(int i=1;i<=n;i++)if(used[i]==mid+1)left--;
		if(left>=now){
			ans=mid;
			top=mid-1;
		}else{
			bot=mid+1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}