#define db(...) fprintf(stderr, __VA_ARGS__)
#include "fish.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const ll OO = 1e18;
struct fish {
int x, w, c, i;
fish() {}
fish(int x, int w, int c, int i) : x(x), w(w), c(c), i(i) {}
};
int n, m;
vector<ll> dp[N][2];
vector<pii> s[N];
ll max_weights(int nn, int mm, vector<int> xx, vector<int> yy, vector<int> ww) {
n = nn;
m = mm;
for(int i = 0; i < m; ++i) {
s[xx[i]].PB({yy[i], ww[i]});
}
for(int i = 0; i < n; ++i) {
s[i].PB({n, 0});
sort(s[i].begin(), s[i].end());
}
ll ans = 0;
for(int i = n - 1; i >= 0; --i) {
vector<fish> f;
for(int j = 0; j < 2; ++j) { dp[i][j].resize(s[i].size(), 0); }
for(int j = 0; j < (int) s[i].size(); ++j) { f.PB(fish(s[i][j].X, s[i][j].Y, 0, j)); }
for(int j = 0; j < (int) s[i + 1].size(); ++j) { f.PB(fish(s[i + 1][j].X, s[i + 1][j].Y, 1, j)); }
sort(f.begin(), f.end(), [](const fish &a, const fish &b) {
return a.x < b.x || (a.x == b.x && a.c > b.c);
});
{ ll axi = -OO, prf = 0;
for(const fish &j : f) {
if(j.c == 0) {
dp[i][0][j.i] = max(0LL, axi + prf);
} else {
axi = max(axi, dp[i + 1][0][j.i] - prf);
prf += j.w;
}
} }
sort(f.begin(), f.end(), [](fish a, fish b) {
return a.x > b.x || (a.x == b.x && a.c < b.c);
});
{ ll axi = -OO, prf = 0;
for(const fish &j : f) {
if(j.c == 0) {
prf += j.w;
dp[i][j.i][1] = max(0LL, axi + prf);
} else {
axi = max(axi, dp[i + 1][j.i][1] - prf);
}
} }
vector<fish> f2;
for(int j = 0; j < (int) s[i + 1].size(); ++j) { f2.PB(fish(s[i + 1][j].X, s[i + 1][j].Y, 1, j)); }
for(int j = 0; j < (int) s[i + 2].size(); ++j) { f2.PB(fish(s[i + 2][j].X, s[i + 2][j].Y, 2, j)); }
sort(f2.begin(), f2.end(), [](const fish &a, const fish &b) {
return a.x < b.x || (a.x == b.x && a.c > b.c);
});
ll axi0 = -OO, axi1 = -OO, prf = 0;
for(const fish &j : f2) {
if(j.c == 1) { prf += j.w; }
else {
axi0 = max(axi0, dp[i + 2][j.i][1]);
axi1 = max(axi1, dp[i + 2][j.i][1] + prf);
}
}
sort(f.begin(), f.end(), [](const fish &a, const fish &b) {
return a.x < b.x || (a.x == b.x && a.c < b.c);
});
prf = 0;
for(const fish &j : f) {
if(j.c == 1) { prf += j.w; }
else {
dp[i][j.i][0] = max(dp[i][j.i][0], max(prf + axi0, axi1));
dp[i][j.i][1] = max(dp[i][j.i][0], dp[i][j.i][1]);
ans = max(ans, dp[i][j.i][1]);
}
}
// db("%d: ", i);
// for(int j = 0; j < (int) s[i].size(); ++j) { db("(%d %lld %lld) ", s[i][j].X, dp[i][0][j], dp[i][1][j]); }
// db("\n");
}
return ans;
}
