#include using namespace std; typedef long long ll; typedef struct{ ll p; ll q; ll num; } CELL; int cmp(CELL a, CELL b){ if(a.q - a.p > b.q - b.p){ return 1; }else{ return 0; } } int main(){ ll n,d,t,l = -100000000,r = 0,m,tm; CELL c[1000] = {}; bool f; cin >> n >> d; for(int i = 0; i < n; i++){ cin >> c[i].p >> c[i].q; c[i].num = i; } sort(c,c+n,cmp); while(l < r){ m = (l+r)/2; tm = 0; t = -1; f = true; for(int i = 0; i < d; i++){ for(int j = 0; j < n; j++){ if(tm >= m + c[j].p && t != j){ t = j; tm += c[j].q - c[j].p; f = false; break; } } if(f){ if(r == m){ r = l; }else{ r = m; } break; } } if(!f){ if(r == m){ l = r; }else{ l = m; } } } cout << l - 1; }