以下、ある問題案の集合 \(S\) における「ジャンルの相異なる面白さ上位 \(X\) 個」といった表現は、厳密には以下の手順によって得られる集合 \(T\) を意味するものとします。

• はじめ、\(T=\emptyset\) とする。\(S\) に含まれる各問題案 \(p\) に対し、面白さの降順に以下を行う。
  • \(|T| < X\) かつ、\(T\) に既に含まれるどの問題案のジャンルも \(p\) のジャンルと異なるならば、\(T\) に \(p\) を追加する。

---

まず、以下のように集合 \(L_i, R_i\) を定義します。

• \(L_i\ (0\leq i\leq N)\) : 問題案 \(1,2,\dots,i\) における、ジャンルの相異なる面白さ上位 \(4\) 個
• \(R_i\ (1\leq i\leq N+1)\) : 問題案 \(i,i+1,\dots,N\) における、ジャンルの相異なる面白さ上位 \(4\) 個

ただし便宜上、ジャンルの相異なる問題が \(4\) 個も存在しない場合、面白さが \(-\infty\) であるような仮想的な問題を適当に追加するものとします。これらは累積 prefix/suffix max の拡張であり、すべての \(i\) に対する \(L_i, R_i\) を \(O(N)\) で前計算することができます。

以下のような方針を考えます。

1. \(K_{i_4}=c\) として、\(c\) の値を全探索する。
2. それぞれの \(c\) の値に対して、\(K_{i_4}=c\) を満たす \(i_4\) の値を全探索する。
3. それぞれの \(i_4\) の値に対して、最適な \(i_3\) の値、およびそのときの答えの最大値を求める。

今、\(c\) が何らかの値に固定されていると仮定して、\(K_{i_4}=c\) を満たす各 \(i_4\) に対して最適な \(i_3\) の値および答えの最大値を求める方法を考えます。

\(i_3=x\) であるときの、\(K_{i_1},K_{i_2},K_{i_3},c\) が相異なるような \(i_1,i_2\) の選び方に対する問題案 \(i_1,i_2,i_3\) の面白さの総和の最大値（ただし、\(K_{i_3}=c\) の場合 \(-\infty\)）を \(M(x)\) とおきます。ここで、最適な \(i_1,i_2\) の値は、前計算した集合 \(L_{x-1}\) からジャンルが \(K_x,c\) のいずれかと一致するようなものを取り除き、残った問題案のうち面白さ上位 \(2\) 個を取ることで求められます。

また、\(f(i_4, d)\) を以下の値と定義します：

• \(d,K_{i_4},K_{i_5},K_{i_6}\) が相異なるような \(i_5,i_6\) の選び方に対する問題案 \(i_4,i_5,i_6\) の面白さの総和の最大値（ただし、\(d=K_{i_4}\) の場合 \(-\infty\)）

今求めたいのは、\(1\leq x < i_4\) を満たす \(x\) に対する \(M(x) + f(i_4, K_x)\) の最大値です。\(x\) の値に応じて \(f(i_4, K_x)\) の値が異なるため、単に \(M(x)\) が最大となる \(x\) を取ればよいわけではないのが厄介ですが、ここで以下の事実が成り立ちます。

• 事実 1：\(M(x) + f(i_4, K_x)\) の最大値を求めるにあたっては、問題案 \(1,2,\dots,i_4-1\) における、ジャンルの相異なる \(M(x)\) の値上位 \(4\) 個のみを考慮すればよい。

詳細な証明は省略しますが、\(f(i_4, K_x)\) の値を \(R_{i_4+1}\) を用いて求める手順を考えると、どんな \(x\) に対しても、「ジャンルの相異なる \(M(x)\) の値上位 \(4\) 個」に含まれる \(x'\) であって \(M(x') \geq M(x)\) かつ \(f(i_4, K_{x'}) \geq f(i_4, K_x)\) なるものが存在することから従います。

「ジャンルの相異なる \(M(x)\) の値上位 \(4\) 個」は、各ノードに配列を載せる Segment Tree によって管理することができます。より具体的には、区間 \([l, r]\) に対応するノードに \(B(l, r):=\)（問題案 \([l, r]\) におけるジャンルの相異なる \(M(x)\) の値上位 \(4\) 個）を載せ、適切なマージ関数を与えることで、任意の \(l, r\) に対して \(B(l, r)\) を \(O(\log N)\) で求められるようになります。

さて、ここまでの考察を踏まえると、ある固定された \(c\) の値に対して 以下のことができるようになります。

• \(O(N)\) の前計算で全ての \(M(x)\) の値を求め、Segment Tree を構築したのち、\(K_{i_4} =c\) を満たす各 \(i_4\) に対してそれぞれ \(O(\log N)\) で答えの最大値を求める。

しかし、\(c\) を全探索したいということを考えると、各 \(c\) の値に対して \(O(N)\) の前計算をするわけにはいきません。そこで、以下の事実に着目します。

• 事実 2：どの \(x\) に対しても、\(c\) の値を \(c=1,2,\dots,N\) と順に変化させていったとき \(M(x)\) の値は \(O(1)\) 回しか変化しない。（また、\(O(1)\) の計算量でその変化点全てを列挙することができる。）

これに関しても詳細な証明は省略しますが、\(M(x)\) の値を \(L_{x-1}\) を用いて求める手順を考えることで示すことができます。

よって、各 \(c\) の値に対して毎度 Segment Tree を一から構築するのではなく、前回の \(c\) の値の時と比べて \(M(x)\) の値が変化したところのみを（Segment Tree の一点更新を用いて）更新することで、全体で \(O(N\log N)\) で本問題を解くことができます。

なお、計算量は \(O(N\log N)\) ですが、定数倍が大きくなりやすいため、実装の際には十分注意してください。例えば、C++ において本問題のように Segment Tree 上に固定長の配列を載せる場合、std::vector を用いると定数倍が悪化するため、std::array などを用いることが一般的に強く推奨されます。

実装例 (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;
}