#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, m; pair <int, int> a[N]; namespace sub2 { /// 1 2 3 /// (1 - 2) + (2 - 3) + (3 - 1) /// 2 - 1 + 3 - 2 + 3 - 1 long long dp[2005][2005]; void solve () { memset(dp, - 0x3f, sizeof dp); for (int i = 1; i <= n; i++) { dp[i][1] = a[i].first + 1LL * 2 * a[i].second; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); if (j < m) { dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1].first - (j + 1 == m ? 1LL * 2 * a[i + 1].second : 0)); } } } long long ans = - 1e18; for (int i = m; i <= n; i++) { ans = max(ans, dp[i][m]); } cout << ans; } } namespace sub3 { int decompress[N], pos[N]; struct FenwickTree { long long sum[4 * N]; int cnt[4 * N]; void upd (int u, int val, int delta) { for (int i = u; i <= n; i+= i&-i) { sum[i]+= val; cnt[i]+= delta; } } long long walk (int num) { long long ans = 0; int cur = 0, pos = 0; for (int i = 20; i >= 0; i--) { if (pos + (1 << i) <= n && cur + cnt[pos + (1 << i)] <= num) { ans+= sum[pos + (1 << i)]; cur+= cnt[pos + (1 << i)]; pos+= (1 << i); } } return ans; } } fwt; int l = 1, r = 0; void MO(int L, int R) { while (l > L) { l--; fwt.upd(pos[l], a[l].first, 1); } while (l < L) { fwt.upd(pos[l], - a[l].first, - 1); l++; } while (r < R) { r++; fwt.upd(pos[r], a[r].first, 1); } while (r > R) { fwt.upd(pos[r], - a[r].first, - 1); r--; } } long long opt_ans[N]; void DnC(int L, int R, int opL, int opR) { if (L > R) return; int mid = L + R >> 1; pair <long long, int> opt = make_pair (- 1e18, opL); for (int i = opL; i <= min(mid - m + 1, opR); i++) { MO(i + 1, mid - 1); long long res = fwt.walk(m - 2) + a[i].first + a[mid].first + 1LL * 2 * a[i].second - 1LL * 2 * a[mid].second; if (opt.first < res) { opt.first = res; opt.second = i; } } opt_ans[mid] = opt.first; DnC(L, mid - 1, opL, opt.second); DnC(mid + 1, R, opt.second, opR); } void solve () { vector <pair <int, int>> values; for (int i = 1; i <= n; i++) { values.push_back({- a[i].first, i}); } sort (values.begin(), values.end()); values.resize(unique(values.begin(), values.end()) - values.begin()); for (int i = 0; i < values.size(); i++) { decompress[i + 1] = - values[i].first; pos[values[i].second] = i + 1; } DnC(1, n, 1, n); long long ans = - 1e18; for (int i = 1; i <= n; i++) { ans = max(ans, opt_ans[i]); } cout << ans; } } int32_t main () { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("joi19_cake3.inp", "r", stdin); // freopen("joi19_cake3.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second; sort (a + 1, a + 1 + n, [&] (pair <int, int> u, pair <int, int> v) { return u.second < v.second; }); return sub3::solve(), 0; return 0; }