#include using namespace std; using ll = long long; const ll MOD = 1000000007; using P = pair; #define rep(i, n) for(int i = 0; i < n; i++) #define all(x) (x).begin(),(x).end() templatebool chmax(T&a, const T&b){if(a<=b){a=b;return 1;}return 0;} int main(){ int n,d; cin >> n >> d; vector

pq(n); rep(i,n){ cin >> pq[i].first >> pq[i].second; pq[i].second -= pq[i].first; } sort(all(pq)); int be = -100000001, en = 0; while(en-be>1){ int md = (be+en)/2, now = 0; int pre = -1; bool b = true; rep(i,d){ int ma = -MOD, flag = -1; rep(j,n){ if(now - pq[j].first < md) break; if(j == pre) continue; if(chmax(ma,pq[j].second)) flag = j; } if(flag < 0){ b = false; break; } now += ma; pre = flag; //cout << pre << " "; } //cout << endl; if(b) be = md; else en = md; } cout << be << endl; return 0; }