#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
#define int long long  
using namespace std;

const int maxn=2e5; 
int n,c,t[maxn+5],d[maxn+5]; 
int check(int mid) {
	int cnt1=0,cnt2=0;
	for (int i=1;i<=n;i++) {
		int x=(t[i]+d[i]-1)/d[i];
		if (x<mid) {
			cnt1+=x; 
		} else if (x==mid) {
			cnt1+=x;
			cnt2++; 
		} else {
			int lst=t[i]-mid*d[i]; 
			cnt1+=mid+lst; 
			cnt2+=lst+1;  
		}
		if (cnt2>c) return 0;
		if (cnt1>mid*c) return 0; 
	} 
	return 1; 
} 
signed main() {
	scanf("%lld %lld",&n,&c);
	for (int i=1;i<=n;i++) scanf("%lld %lld",&t[i],&d[i]); 
	int l=1,r=2e14,ans=0;
	while (l<=r) {
		int mid=(l+r)>>1;
		if (check(mid)) ans=mid,r=mid-1;
		else l=mid+1; 
	}
	cout<<ans-1; 
	return 0;
}