#include<bits/stdc++.h>
#include "fish.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
ll max_weights(int n, int m, vector<int>X, vector<int>Y, vector<int>W){
bool is_sub1 = true;
for(int& x : X){
if(x & 1){
is_sub1 = false;
break;
}
}
if(is_sub1){
return accumulate(W.begin(), W.end(), 0LL);
}
if(*max_element(X.begin(), X.end()) <= 1){
if(n > 2){
ll sum = 0;
vector<vector<pair<int, int>>>p(2);
for(int i = 0; i < m; i++){
if(X[i] == 1){
sum += W[i];
p[1].emplace_back(Y[i], W[i]);
}
else{
p[0].emplace_back(Y[i], W[i]);
}
}
p[1].emplace_back(-1, 0);
sort(p[0].begin(), p[0].end());
sort(p[1].begin(), p[1].end());
p[1].emplace_back(n, 0);
ll ans = sum;
for(int i = 0, j = 0; j + 1 < p[1].size(); j++){
sum -= p[1][j].second;
if(p[1][j].first == p[1][j + 1].first){
continue;
}
while(i < p[0].size() && p[0][i].first < p[1][j + 1].first){
sum += p[0][i].second;
i++;
}
maximize(ans, sum);
}
return ans;
}
ll sum_0 = 0, sum_1 = 0;
for(int i = 0; i < m; i++){
if(X[i] == 0){
sum_0 += W[i];
}
else{
sum_1 += W[i];
}
}
return max(sum_0, sum_1);
}
if(*max_element(Y.begin(), Y.end()) == 0){
vector<int>w(n + 1, 0);
for(int i = 0; i < m; i++){
w[X[i] + 1] = W[i];
}
vector<ll>dp(3, -INF);
dp[1] = 0;
for(int i = 1; i <= n; i++){
vector<ll>ndp(3);
ndp[0] = max({dp[0], dp[1] + w[i - 1], dp[2]});
ndp[1] = max(dp[1], dp[2]);
ndp[2] = dp[0] + w[i];
swap(dp, ndp);
}
return max({dp[0], dp[1], dp[2]});
}
if(n <= 3000){
vector<vector<ll>>w(n + 2, vector<ll>(n + 2, 0));
for(int i = 0; i < m; i++){
w[X[i] + 1][Y[i] + 1] = W[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
w[i][j] += w[i][j - 1];
}
}
vector<vector<ll>>dp(n + 1, vector<ll>(3, -INF));
for(int i = 0; i <= n; i++){
dp[i][0] = 0;
}
for(int i = 1; i <= n; i++){
vector<vector<ll>>ndp(n + 1, vector<ll>(3, -INF));
ll init_sub_12 = -INF, temp = -INF;
for(int j = 0; j <= n; j++){
maximize(ndp[0][0], dp[j][0]);
maximize(init_sub_12, dp[j][0] - w[i - 1][j]);
}
for(int j = 1; j <= n; j++){
maximize(temp, dp[j][1] - w[i - 1][j]);
ndp[j][1] = max(ndp[j][2] = max(ndp[0][0], init_sub_12 + w[i - 1][j]), temp + w[i - 1][j]);
maximize(ndp[j][0], max(dp[j][1], dp[j][2]) + w[i][j]);
}
temp = 0;
for(int j = n; j > 0; j--){
maximize(temp, max(dp[j][1], dp[j][2]) + w[i][j]);
maximize(ndp[j][2], temp - w[i][j]);
}
swap(dp, ndp);
}
ll ans = 0;
for(int i = 0; i <= n; i++){
maximize(ans, max({dp[i][0], dp[i][1], dp[i][2]}));
}
return ans;
}
vector<vector<pair<int, ll>>>fish(n + 2, vector<pair<int, ll>>(1, make_pair(0, 0)));
for(int i = 0; i < m; i++){
fish[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
}
for(int i = 1; i <= n; i++){
sort(fish[i].begin(), fish[i].end());
for(int j = 1; j < fish[i].size(); j++){
fish[i][j].second += fish[i][j - 1].second;
}
}
auto prefix_sum = [&] (int x, int y){
return (*prev(lower_bound(fish[x].begin(), fish[x].end(), make_pair(y + 1, -1LL)))).second;
};
vector<vector<int>>index(n + 1, vector<int>(1, 0));
for(int i = 1; i <= n; i++){
for(int j = -1; j < 2; j++){
for(auto& [y, foo] : fish[i + j]){
index[i].emplace_back(y);
}
}
sort(index[i].begin(), index[i].end());
index[i].resize(unique(index[i].begin(), index[i].end()) - index[i].begin());
}
vector<vector<ll>>dp(1, vector<ll>(3, -INF));
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
vector<vector<ll>>ndp(index[i].size(), vector<ll>(3, -INF));
ll init_sub_12 = 0, temp = -INF;
for(int j = 0; j < dp.size(); j++){
maximize(ndp[0][0], dp[j][0]);
maximize(init_sub_12, dp[j][0] - prefix_sum(i - 1, index[i - 1][j]));
}
for(int j = 1, p = 0; j < index[i].size(); j++){
while(p < dp.size() && index[i - 1][p] <= index[i][j]){
maximize(temp, dp[p][1] - prefix_sum(i - 1, index[i - 1][p]));
p++;
}
ndp[j][1] = max(ndp[j][2] = max(ndp[0][0], init_sub_12 + prefix_sum(i - 1, index[i][j])), temp + prefix_sum(i - 1, index[i][j]));
}
ll other_temp = temp = -INF;
for(int j = int(ndp.size()) - 1, p = int(dp.size()) - 1; j > -1; j--){
while(p > -1 && index[i - 1][p] >= index[i][j]){
maximize(temp, max(dp[p][1], dp[p][2]) + prefix_sum(i, index[i - 1][p]));
maximize(other_temp, max(dp[p][1], dp[p][2]));
p--;
}
maximize(ndp[j][2], temp - prefix_sum(i, index[i][j]));
maximize(ndp[j][0], other_temp + prefix_sum(i, index[i][j]));
}
swap(dp, ndp);
}
ll ans = 0;
for(int i = 0; i < dp.size(); i++){
maximize(ans, max({dp[i][0], dp[i][1], dp[i][2]}));
}
return ans;
}
