(dựa theo hình ảnh này đổi ra chữ

#include <bits/stdc++.h>
#define N int(5e5)
#define ll long long
using namespace std;
struct gift
{
    int a, w, id;
};
gift b[N + 3];
ll T[N + 3], dp[N + 3], ans;
int n;
map<int, int> M;
bool cmp_label(gift X, gift Y)
{
    return X.a < Y.a;
}

bool cmp_id(gift X, gift Y)
{
    return X.id < Y.id;
}

ll get(int x)
{
    ll res = 0;
    while (x > 0)
    {
        res = max(res, T[x]);
        x = x - (x & (-x));
    }
    return res;
}

void update(int x, ll delta)
{
    while (x <= N)
    {
        T[x] = max(T[x], delta);
        x = x + (x & (-x));
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("qua.inp", "r", stdin);
    freopen("qua.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].a >> b[i].w;
        b[i].id = i;
    }
    /// nen nhãn b[i].a xuống để nhãn có giá trị <=n
    sort(b + 1, b + n + 1, cmp_label);
    for (int i = 1; i <= n; i++)
    if (M[b[i].a] == 0)
    {
        int x = M.size();
        M[b[i].a] = x;
        b[i].a = x;
    }
    else b[i].a = M[b[i].a];
    /// sau khi nen xong thi sap xem lai day quay ve trinh tu cu
    sort(b + 1, b + n + 1, cmp_id);
    /// tim ket qua
    for (int i = 1; i <= n; i++)
    {
        ll x = get(b[i].a - 1);
        dp[i] = x + b[i].w;
        ans = max(ans, dp[i]);
        update(b[i].a, dp[i]);
    }
    cout << ans;
    return 0;
}