For simplicity, we will call a problem candidate simply a “problem.” For a set of problem \(S\), define the “top \(X\) (interesting) problems with different genres” among them as the set \(T\) obtained by the following procedure:

• Initially, let \(T=\emptyset\). For each problem \(p\) in \(S\), perform the following in descending order of their interests.
  • Insert \(p\) to \(T\) if \(|T| < X\) and no problem in \(T\) has the same genre as \(p\).

---

Define sets \(L_i\) and \(R_i\) as follows:

• \(L_i\ (0\leq i\leq N)\): the top four problems with different genres among problems \(1,2,\dots,i\)
• \(L_i\ (0\leq i\leq N)\): the top four problems with different genres among problems \(i,i+1,\dots,N\)

For convenience, if there are less than four problems with pairwise distinct genres, add virtual problem(s) with interest \(-\infty\) to the set. These sets are a variant of cumulative prefix/suffix max, and \(L_i\) and \(R_i\) for all \(i\) can be found in \(O(N)\) time.

Consider the following approach:

1. We try all candidates for \(K_{i_4}\), which we denote by \(c\).
2. For each value of \(c\), find all indices \(i_4\) with \(K_{i_4}=c\).
3. For each value of \(i_4\), find the optimal \(i_3\) and the maximum value for the answer.

Supposing that \(c\) is fixed, let us consider how to find, for each \(i_4\) with \(K_{i_4}=c\), the optimal \(i_3\) and the maximum value for the answer.

Let \(M(x)\) be the maximum total interest of problems \(i_1,i_2\), and \(i_3\) such that \(i_3=x\), and \(K_{i_1},K_{i_2},K_{i_3},c\) have different genres among the choices of \(i_1\) and \(i_2\) (or \(-\infty\) if \(K_{i_3}=c\)). The optimal choice can be obtained by removing from the precalculated set \(L_{x-1}\) the problems whose genres are either \(K_x\) and \(c\), and picking the two most interesting problems from the rest.

Also, define \(f(i_4, d)\) as:

• the maximum total interest of problems \(i_4,i_5\), and \(i_6\) such that \(d,K_{i_4},K_{i_5},K_{i_6}\) have different genres among the choices of \(i_1\) and \(i_2\) (or \(-\infty\) if \(d=K_{i_4}\)).

What we want to find is the maximum value of \(M(x) + f(i_4, K_x)\) for \(x\) with \(1\leq x < i_4\). Since \(f(i_4, K_x)\) is dependent on \(f(i_4, K_x)\), we cannot simply pick \(x\) that maximizes \(M(x)\); however, we have the following fact:

• Fact 1: to find the maximum value of \(M(x) + f(i_4, K_x)\), it is sufficient to consider the top four interesting problems with different genres among problems \(1,2,\dots,i_4-1\).

We omit the detailed proof here, but this follows from the existence, for all \(x\), the existence of \(x'\) in “the top four values of \(M(x)\) with different genres” such that \(M(x') \geq M(x)\) and \(f(i_4, K_{x'}) \geq f(i_4, K_x)\).”

“The top four values of \(M(x)\) with different genres” can be managed in a segment tree that stores an array in each node. More specifically, we can let the node for segment \([l,r]\) maintain \(B(l, r):=\) (the top four values of \(M(x)\) with different genres among problems \([l, r]\)) and define an appropriate merge function so that \(B(l, r)\) can be found for any \(l\) and \(r\) in \(O(\log N)\) time.

Based on the observations so far, we can now perform the following operation for a fixed \(c\):

• Spend \(O(N)\) time to find all values of \(M(x)\) and construct a segment tree. For each \(i_4\) with \(K_{i_4} =c\), find the maximum answer in \(O(N\log N)\) time.

However, since we need to search all \(c\) exhaustively, we cannot spend \(O(N)\) time for each \(c\). Instead, we notice the following fact:

• Fact 2: for all \(x\), the value \(M(x)\) changes only \(O(1)\) times as we scan as \(c=1,2,\dots,N\). (Moreover, the transition points can be enumerated in \(O(1)\) time.

We also omit the proof here, but it can be proved by tracking the procedure when finding \(M(x)\) based on \(L_{x-1}\).

Therefore, instead of constructing a segment tree from scratch for each \(c\), we may update \(M(x)\) only for those that have changed (using the element-wise update operation on a segment tree), so that the problem can be solved in \(O(N\log N)\) time.

Note that while the complexity is \(O(N\log N)\), the constant factor can be large, so beware of it when implementing. For example, when we store a fixed-size array to segment tree as in this problem in C++, using std::vector worsen the constant factor; it is strongly recommended in general to use std::array instead.

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;

using ll = long long;

const ll inf = 1LL << 60;

const int SZ = 4;
using S = array<pair<ll, ll>, SZ>;

S op(const S &a, const S &b) {
    array<pair<ll, ll>, SZ * 2> c;
    copy(a.begin(), a.end(), c.begin());
    copy(b.begin(), b.end(), c.begin() + SZ);
    sort(c.rbegin(), c.rend());
    S res;
    int it = 0;
    for (int i = 0; i < SZ; i++) {
        while (true) {
            bool ok = true;
            for (int j = 0; j < i; j++) {
                if (res[j].second == c[it].second) {
                    ok = false;
                    break;
                }
            }
            if (ok) break;
            it++;
        }
        res[i] = c[it++];
    }
    return res;
}

S e() {
    return {
            make_pair(-inf, -1),
            make_pair(-inf, -2),
            make_pair(-inf, -3),
            make_pair(-inf, -4)
    };
}

S single(ll k, ll a) {
    a = max(a, -inf);
    S res = e();
    res[0] = {a, k};
    return res;
}

S add(S s, ll k, ll a) {
    for (int i = 0; i < SZ; i++) {
        if (s[i].second == k) {
            s[i].first = max(s[i].first, a);
            sort(s.rbegin(), s.rend());
            return s;
        }
    }
    array<pair<ll, ll>, SZ + 1> tmp;
    copy(s.begin(), s.end(), tmp.begin());
    tmp[SZ] = {a, k};
    sort(tmp.rbegin(), tmp.rend());
    for (int i = 0; i < SZ; i++) {
        s[i] = tmp[i];
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> k(n), a(n);
    vector<vector<int>> ls(n);
    for (int i = 0; i < n; i++) {
        cin >> k[i] >> a[i];
        --k[i];
        ls[k[i]].push_back(i);
    }

    vector<S> l(n + 1), r(n + 1);
    l[0] = r[n] = e();
    for (int i = 0; i < n; i++) {
        l[i + 1] = add(l[i], k[i], a[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        r[i] = add(r[i + 1], k[i], a[i]);
    }

    vector<ll> ori(n);
    vector<S> init(n);
    vector<vector<pair<int, ll>>> change(n);
    for (int i = 0; i < n; i++) {
        vector<pair<ll, ll>> cand;
        for (auto p: l[i]) {
            if (p.second != k[i]) cand.push_back(p);
        }
        assert(cand.size() >= 3);
        ori[i] = a[i] + cand[0].first + cand[1].first;
        init[i] = single(k[i], ori[i]);
        for (int j = 0; j < 2; j++) {
            if (cand[j].second < 0) continue;
            ll now = ori[i] - cand[j].first + cand[2].first;
            change[cand[j].second].emplace_back(i, now);
        }
    }

    atcoder::segtree<S, op, e> st(init);
    ll ans = -1;
    for (int c = 0; c < n; c++) {
        for (auto [i, now]: change[c]) {
            st.set(i, single(k[i], now));
        }
        for (int i: ls[c]) {
            vector<pair<ll, ll>> cand;
            for (auto p: r[i + 1]) {
                if (p.second != k[i]) cand.push_back(p);
            }
            assert(cand.size() >= 3);
            S best = st.prod(0, i);
            for (auto p: best) {
                if (p.second == k[i]) continue;
                ll now;
                if (p.second == cand[0].second) {
                    now = cand[1].first + cand[2].first;
                } else if (p.second == cand[1].second) {
                    now = cand[0].first + cand[2].first;
                } else {
                    now = cand[0].first + cand[1].first;
                }
                now += p.first + a[i];
                ans = max(ans, now);
            }
        }
        for (auto [i, _]: change[c]) {
            st.set(i, single(k[i], ori[i]));
        }
    }

    cout << ans << endl;
}