Đầu tiên ta sắp xếp lại các điểm tăng dần theo trục ~x~.

Dễ thấy ta có thể biến đổi phương trình đề bài lại thành ~\sum_{i \in S}y_i + min(x_i) - max(x_i)~. Vì ~y_i~ luôn dương nên ta gọi ~S[i] = max(\sum_{i \in S}y_i + min(x_i))~. Cụ thể với mỗi vị trí ~i~, ta cộng ~y_i~ lên đoạn ~S[1..i]~ và ~x_i~ lên ~S[i]~, ở phần này ta có thể ứng dụng tổng tiền tố. Kết quả của bài toán sẽ là ~max(max(S[1..i]) - x_i)~ với ~(1 \le i \le n)~

Độ phức tạp: ~O(n \times logn)~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)5e5+228;

int n;
pair<long long, long long> a[N];
long long sum[N];

void solve()
{
    cin >> n;
    for(int i=1; i<=n; ++i)
    {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a+1, a+n+1);
    for(int i=1; i<=n; ++i)
    {
        sum[i] = sum[i-1] + a[i].se;
    }

    long long ma = -1e18, res = -1e18;
    for(int i=1; i<=n; ++i)
    {
        ma = max(ma, -sum[i-1] + a[i].fi);
        res = max(res, sum[i] - a[i].fi + ma);
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    solve();
    return 0;
}