#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<pair<int,int>> states(N);
for (int i=0;i<N;i++) cin >> states[i].first >> states[i].second; // Ai, Bi
const ll INF = 4e18;
ll ans = INF;
// posortowane po Ai i Bi
vector<int> orderA(N), orderB;
iota(orderA.begin(), orderA.end(), 0);
sort(orderA.begin(), orderA.end(), [&](int i,int j){ return states[i].first < states[j].first; });
for (int i=0;i<N;i++) if (states[i].second != -1) orderB.push_back(i);
sort(orderB.begin(), orderB.end(), [&](int i,int j){ return states[i].second < states[j].second; });
// prefix sums dla Ai
vector<ll> prefA(N+1,0);
for (int i=0;i<N;i++) prefA[i+1] = prefA[i] + states[orderA[i]].first;
// prefix sums dla Bi
vector<ll> prefB(orderB.size()+1,0);
for (int i=0;i<(int)orderB.size();i++) prefB[i+1] = prefB[i] + states[orderB[i]].second;
for (int m=0;m<=orderB.size();m++) { // ilu pomagierów kupimy
if (m > orderB.size()) break;
if (m > 0 && prefB[m] >= INF) continue;
// wybieramy K głosów (uwzględniając, że stany pomagierów mogą też być głosem)
// żeby to obsłużyć łatwo: weźmy listę wszystkich Ai, ale dla stanów z kupionym pomagierem weźmy min(Ai,0) w praktyce -> Ai
// implementacja: po prostu wybieramy minK spośród wszystkich stanów
vector<int> used(orderB.begin(), orderB.begin()+m);
vector<bool> mark(N,false);
for (int id: used) mark[id]=true;
// zbieramy wszystkie Ai, a stany z pomagierami są już zaznaczone
vector<int> candidates;
for (int i=0;i<N;i++) candidates.push_back(states[i].first);
sort(candidates.begin(), candidates.end());
if (K > N) continue;
ll sumA = 0;
for (int i=0;i<K;i++) sumA += candidates[i];
ll total = prefB[m] + sumA;
ll time = (total + m) / (m+1); // ceil dzielenia
ans = min(ans, time);
}
cout << ans << "\n";
}
