#include "fish.h"
#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define rf(i, a, b) for (int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ve = vector<T>;
template <typename T>
bool umx(T& a, T b) {
return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umn(T& a, T b) {
return a > b ? a = b, 1 : 0;
}
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e5 + 100;
const int M = 3000;
const int K = 110;
const int mod = 1e9 + 7;
const bool TEST = 1;
void precalc() {}
ve <ll> dp1[N]; // before the i-th is filled, back -- all filled
ve <ll> dp2[N]; // before the i-th is filled, back -- all filled
ve <ll> zero[N]; // i points is used
ve <pii> YY[N];
bool vs[M][M];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
// freopen("output.txt", "w", stdout);
// if(N <= 4e3) {
// for (int i = 0; i < M; i++) {
// vs[X[i]][Y[i]] = 1;
// }
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// if (!vs[i][j]) {
// X.pb(i);
// Y.pb(j);
// W.pb(0);
// }
// }
// }
// }
for (int i = 0; i < sz(Y); i++) {
dp1[X[i]].pb(-OO);
dp2[X[i]].pb(-OO);
zero[X[i]].pb(-OO);
YY[X[i]].pb({Y[i], W[i]});
}
for (int i = 0; i < N; i++) {
sort(all(YY[i]));
dp1[i].pb(-OO);
dp2[i].pb(-OO);
zero[i].pb(-OO);
}
for (int i = 0; i < sz(dp1[0]); i++) {
dp1[0][i] = 0;
dp2[0][i] = 0;
zero[0][i] = 0;
}
for (int i = 1; i < N; i++) {
// from dp1
{ // to zero
int Z = 0;
ll S = 0;
for (int j = 0; j < sz(YY[i - 1]); j++) {
while (Z < sz(YY[i]) && YY[i - 1][j].fi - 1 >= YY[i][Z].fi) {
S += YY[i][Z].se;
Z++;
}
umx(zero[i][Z], dp1[i - 1][j] + S);
}
for (; Z < sz(YY[i]); Z++) S += YY[i][Z].se;
umx(zero[i].back(), dp1[i - 1].back() + S);
}
{ // to dp1
umx(dp1[i].back(), dp1[i - 1].back());
ll S = 0;
int ptr = sz(YY[i - 1]) - 1;
ll mx = dp1[i - 1].back();
for (int j = sz(YY[i]) - 1; j >= 0; j--) {
while(ptr >= 0 && YY[i - 1][ptr].fi - 1 >= YY[i][j].fi) {
mx = max(mx, dp1[i - 1][ptr] - S);
ptr--;
}
S += YY[i][j].se;
umx(dp1[i][j], mx + S);
}
}
// from zero
for (int j = 0; j <= sz(YY[i - 1]); j++) umx(zero[i][0], zero[i - 1][j]); // to zero
{ // to dp1 & dp2
{ // back
ll S = 0;
for (int j = sz(YY[i - 1]); j >= 0; j--) {
umx(dp1[i].back(), S + zero[i - 1][j]);
umx(dp2[i].back(), S + zero[i - 1][j]);
if (j - 1 >= 0) S += YY[i - 1][j - 1].se;
}
}
ll res = 0;
for (int j = 0; j <= sz(YY[i - 1]); j++) umx(res, zero[i - 1][j]);
ll S = 0;
ll mx = zero[i - 1][0];
int ptr = 0;
for (int j = 0; j < sz(YY[i]); j++) {
while (ptr < sz(YY[i - 1]) && YY[i - 1][ptr].fi <= YY[i][j].fi - 1) {
S += YY[i - 1][ptr].se;
ptr++;
umx (mx, zero[i - 1][ptr] - S);
}
umx(dp1[i][j], max(res, mx + S));
umx(dp2[i][j], max(res, mx + S));
}
}
// from dp2
{ // to zero
int Z = 0;
ll S = 0;
for (int j = 0; j < sz(YY[i - 1]); j++) {
while (Z < sz(YY[i]) && YY[i - 1][j].fi - 1 >= YY[i][Z].fi) {
S += YY[i][Z].se;
Z++;
}
umx(zero[i][Z], dp2[i - 1][j] + S);
}
for (; Z < sz(YY[i]); Z++) S += YY[i][Z].se;
umx(zero[i].back(), dp2[i - 1].back() + S);
}
{ // to dp2 & dp1
ll S = 0;
ll mx = 0;
int ptr = 0;
for (int j = 0; j < sz(YY[i]); j++) {
while (ptr < sz(YY[i - 1]) && YY[i - 1][ptr].fi <= YY[i][j].fi - 1) {
umx (mx, dp2[i - 1][ptr] - S);
S += YY[i - 1][ptr].se;
ptr++;
}
umx(dp2[i][j], mx + S);
umx(dp1[i][j], mx + S);
}
for (; ptr < sz(YY[i - 1]); ptr++) {
umx(mx, dp2[i - 1][ptr] - S);
S += YY[i - 1][ptr].se;
}
umx(mx, dp2[i - 1].back() - S);
umx(dp2[i].back(), mx + S);
umx(dp1[i].back(), mx + S);
}
}
// cout << zero[2][1] << endl;
ll ans = 0;
fe(x, dp1[N - 1]) umx(ans, x);
fe(x, dp2[N - 1]) umx(ans, x);
fe(x, zero[N - 1]) umx(ans, x);
return ans;
}
