#include <bits/stdc++.h> using namespace std; #define ll long long #define ii pair<int, int> #define fi first #define se second #define ve vector #define mini(a, b) a = min(a, b) #define maxi(a, b) a = max(a, b) #define all(x) x.begin(), x.end() #define _ << ' ' << #define err(x) cerr << (#x) << " = " << (x) << '\n' #define fo(i,a,b) for (int i = (a); i <= (b); ++i) #define fd(i,a,b) for (int i = (a); i >= (b); --i) #define pb push_back #define siz(x) (int)((x).size()) #define ld long double bool Mbe; const int N = 1e6+5, M = 1e2+5, inf = 1e9+10, mod = 1e9+7; struct node { int cnt, lc, rc; ll sum; node() { cnt = lc = rc = sum = 0; } }; node t[N*20]; int he; ve<int> z; int clone(int p = 0) { t[++he] = t[p]; return he; } void pull(int p) { t[p].cnt = t[t[p].lc].cnt + t[t[p].rc].cnt; t[p].sum = t[t[p].lc].sum + t[t[p].rc].sum; } int init(int p, int l, int r) { int k = clone(p); if (l == r) return k; int mid = (l + r) >> 1; t[k].lc = init(t[p].lc, l, mid); t[p].rc = init(t[p].rc, mid+1, r); return k; } int upd(int p, int l, int r, int pos, int val) { int k = clone(p); if (l == r) { t[k].cnt++; t[k].sum += val; return k; } int mid = (l + r) >> 1; if (pos <= mid) t[k].lc = upd(t[p].lc, l, mid, pos, val); else t[k].rc = upd(t[p].rc, mid+1, r, pos, val); pull(k); return k; } ll get(int pL, int pR, int l, int r, int k) { if (k == 0 || t[pL].cnt == t[pR].cnt) return 0; if (k >= t[pR].cnt - t[pL].cnt) return t[pR].sum-t[pL].sum; if (l == r) return min(k, t[pR].cnt - t[pL].cnt) * z[l-1]; int mid = (l + r) >> 1; ll ans = get(t[pL].rc, t[pR].rc, mid+1, r, k); k -= min(k, t[t[pR].rc].cnt - t[t[pL].rc].cnt); return ans + get(t[pL].lc, t[pR].lc, l, mid, k); } int n, m, root[N]; ll get(int l, int r, int k) { return get(root[l-1], root[r], 1, n, k); } ii a[N]; ll ans = -1e18; ll cost(int l, int r) { int nx = min(r-l+1, m); return get(l, r, nx) - 2LL * (a[r].se - a[l].se); } void dnc(int l, int r, int optl, int optr) { if (l > r) return; int mid = (l + r) >> 1; pair<ll,int> best={-1e18,-1}; fo(i,optl,min(mid-m+1,optr)) { best=max(best,pair<ll,int>(cost(i, mid), i)); } maxi(ans, best.fi); dnc(l, mid-1, optl, best.se); dnc(mid+1, r, best.se, optr); } void solve() { cin >> n >> m; root[0] = clone(0); root[0] = init(root[0], 1, n); fo(i,1,n) { cin >> a[i].fi >> a[i].se; z.pb(a[i].fi); } sort(all(z)); z.resize(unique(all(z))-z.begin()); sort(a+1, a+n+1, [&](ii x, ii y)->bool{ if (x.se == y.se) return 0; return x.se < y.se; }); fo(i,1,n) { a[i].fi = upper_bound(all(z), a[i].fi)-z.begin(); root[i] = upd(root[i-1], 1, n, a[i].fi, z[a[i].fi-1]); } dnc(1,n,1,n); cout << ans; } bool Med; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("a.inp", "r")) { freopen("a.inp", "r", stdin); freopen("a.out", "w", stdout); } else { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } solve(); cerr << "mem = " << abs(&Med-&Mbe)/1024.0/1024.0 << " mb\n"; cerr << "time = " << clock()/1000.0 << "ms\n"; return 0; }

cake3.cpp: In function 'int main()':
cake3.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("a.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake3.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("a.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~