#include <bits/stdc++.h> #define C first #define V second using namespace std; typedef pair<long long, long long> ii; int n, m; long long op[300005]; ii arr[200005]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; m -= 2; for(int i = 1;i <= n;i++) cin >> arr[i].V >> arr[i].C; sort(arr+1,arr+n+1); long long ans = -1e18; fill(op,op+300004, n); op[0] = 1; for(int bit = (1<<17);bit >= 1;bit >>= 1){ for(int s = bit;s < n - m;s += 2*bit){ int L, R; L = op[s-bit]; R = op[s+bit]; L = max(s+1, L); long long bestValue = -1e18; long long bestPos = -1; priority_queue<long long, vector<long long>, greater<long long> > pq; long long acc = 0; for(int e = L;e <= R;e++){ if((int) pq.size() >= m){ if((int) pq.size() > m){ acc -= pq.top(); pq.pop(); } long long val = acc + arr[s].V + arr[e].V - 2*arr[e].C + 2*arr[s].C; ans = max(ans, val); if(bestValue < val){ bestValue = val; bestPos = e; } } pq.push(arr[e].V); acc += arr[e].V; } op[s] = bestPos; } } cout << ans; }