#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));
ndp[0][0] = dp[0][0];
ll init_12 = 0, init_sub_12 = -INF;
for(int j = 0; j <= n; j++){
maximize(init_12, dp[j][0]);
maximize(init_sub_12, dp[j][0] - w[i - 1][j]);
}
ll temp = -INF;
for(int j = 1; j <= n; j++){
maximize(temp, dp[j][1] - w[i - 1][j]);
ndp[j][1] = max(ndp[j][2] = max(init_12, 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]);
maximize(ndp[0][0], dp[j][0]);
}
temp = 0;
for(int j = n; j > 0; j--){
maximize(temp, 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;
}
}
