#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define int long long int
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ln '\n'
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    for(auto &x : c) out<<x<<" ";
    out<<"}"; return out;
}

const int MOD = 1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, c;

vector<pii> tasks;

bool check(int val){

	priority_queue<pii> q;
	rep(i, 0, tasks.size()){
		q.push(tasks[i]);
	}

	// max d, then t

	int consumed = 0;
	// consumed should be <= val for each
	int final = 0;

	while(!q.empty()){
		auto t = q.top();
		q.pop();

		if(t.second > MOD){
			if(consumed < c*val) consumed += 1;
			else final += 1;
			continue;
		}

		int to_almost_fin = t.second / t.first;
		to_almost_fin = min(to_almost_fin, val);
		to_almost_fin = min(to_almost_fin, c * val - consumed);
		consumed += to_almost_fin;
		t.second -= to_almost_fin * t.first;
		// t.second is the remaining time
		if(to_almost_fin == val){
			final += 1;
			t.second -= min(t.first, t.second);
			final += t.second;
			continue;
		}
		if(t.second>0){
			q.push({t.second, MOD+t.second});
		}
	}

	if(final > c) return 0;
	return 1;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	cin >> n >> c;

	rep(i, 0, n){
		int t, d;
		cin >> t >> d;
		tasks.push_back({d,t});
	}

	sort(all(tasks));

	int l = 0, r = (3e14+c-1)/c;

	while(l<r){
		int mid = (l+r)/2;
		if(check(mid)){
			r = mid;
		}
		else{
			l = mid+1;
		}
	}

	cout << l << endl;


	return 0;
}