#include <vector>
#include <iostream>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vector<int> P(N), Q(N);
	for (int i = 0; i < N; ++i) {
		cin >> P[i] >> Q[i];
	}
	int l = 0, r = (1 << 29);
	while (r - l > 1) {
		int m = (l + r) >> 1;
		int genki = 0, prechoice = -1;
		bool flag = true;
		for (int i = 0; i < D; ++i) {
			int optchoice = -1, optscore = -(1 << 30);
			for (int j = 0; j < N; ++j) {
				if (j != prechoice && genki + P[j] <= m && optscore < Q[j] - P[j]) {
					optchoice = j;
					optscore = Q[j] - P[j];
				}
			}
			if (optchoice == -1) {
				flag = false;
				break;
			}
			genki -= optscore;
			prechoice = optchoice;
		}
		if (flag) r = m;
		else l = m;
	}
	cout << -r << endl;
	return 0;
}