#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;


bool check(int n, LL m, int c, vector<PII> a)
{
	int w = min(n, c);
	__int128 time = (__int128)w * m;;
	vector<tuple<int, int, int>> v;
	FOR (i, 0, n)
	{
		auto& [d, t] = a[i];
		int cnt = t / d;
		if (m < cnt)
			cnt = m;
		if (time < cnt)
			cnt = time;
		t -= cnt * d;
		time -= cnt;
		
		d = min(d, t);
		v.PB({d, t, cnt});
	}
	sort(ALL(v), greater());
	LL last = 0;
	FOR (i, 0, n)
	{
		auto [d, t, cnt] = v[i];
		if (t == 0)
			continue;
		if (cnt != m && time != 0)
		{
			time--;
			t -= d;
			last += t;
		}
		else
		{
			last += max(0, t - d) + 1;
		}
	}
	return last <= c;
}

const int INF = 1e9 + 47;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, c;
	cin >> n >> c;
	vector<PII> a(n);
	FOR(i, 0, n)
		cin >> a[i].S >> a[i].F;
	
	sort(ALL(a), greater());
	
	LL l = -1, r = (LL)n * INF;
	
	while(r - l > 1)
	{
		LL m = (l + r) / 2;
		if(check(n, m, c, a))
			r = m;
		else
			l = m;
	}
	cout << r << "\n";
	
	return 0;
}