#include "fish.h"
using namespace std;
#include<bits/stdc++.h>
#define ll long long
long long subtask1(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W){
long long ans=0;
for(int i=0; i<M; i++){
ans+=W[i];
}
return ans;
}
long long subtask2(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W){
vector<pair<int,int>> c0;
vector<pair<int,int>> c1;
long long sum0=0;
long long sum1=0;
for(int i=0; i<M; i++){
if(X[i]==0){
c0.push_back({Y[i], W[i]});
sum0+=W[i];
}
else{
c1.push_back({Y[i], W[i]});
sum1+=W[i];
}
}
if(N==2){
return max(sum0, sum1);
}
sort(c1.begin(), c1.end());
sort(c0.begin(), c0.end());
long long ans=max(sum0, sum1);
long long mom=sum1;
int j=0;
for(int i=0; i<(int)c1.size(); i++){
while(j<(int)c0.size() && c0[j].first<c1[i].first){
mom+=c0[j].second;
j++;
}
ans=max(ans, mom);
mom-=c1[i].second;
}
return ans;
}
long long gain(int h1, int free1, int h2, int free2, vector<pair<int,int> >& c1, vector<pair<int,int> >& c2){
//wand von 1 ist grösser
int wallh=c1[h1].first;
ll ans=0;
for(int i=max(h2, (int)c2.size()-free2); i<(int)c2.size(); i++){
if(c2[i].first < wallh){
ans+= c2[i].second;
}
}
return ans;
}
const int INF=1e9+7;
long long subtask3(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<vector<pair<int,int> > > c(n);
for(int i=0; i<m; i++){
c[x[i]].push_back({y[i], w[i]});
}
int maxh=0;
for(int i=0; i<n; i++){
sort(c[i].begin(), c[i].end());
c[i].push_back({INF, 0});
maxh=max(maxh, (int)c[i].size());
}
vector<vector<vector<ll> > > dp(n, vector<vector<ll> > (maxh, vector<ll> (maxh)));
for(int i=1; i<n; i++){
for(int h=0; h<(int)c[i].size(); h++){
for(int free=0; free<(int)c[i].size()-h; free++){
for(int h0=0; h0<(int)c[i-1].size(); h0++){
for(int free0=0; free0<(int)c[i-1].size()-h0; free++){
ll g=0;
if(c[i][h].first>c[i-1][h0].first){
g = gain(h, free, h0, free0, c[i], c[i-1]);
}
else{
g = gain(h0, free0, h, free, c[i-1], c[i]);
}
dp[i][h][free] = max(dp[i][h][free], dp[i-1][h0][free0] + g);
}
}
}
}
}
ll ans=0;
for(int h=0; h<maxh; h++){
for(int free=0; free<maxh; free++){
ans=max(ans, dp[n-1][h][free]);
}
}
return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
if(N==1) return 0;
bool sub1=true;
bool sub2=true;
for(int i=0; i<M; i++){
if(X[i]%2==1){
sub1=false;
}
if(X[i]>1){
sub2=false;
}
}
if(sub1){
return subtask1(N, M, X, Y, W);
}
if(sub2){
return subtask2(N, M, X, Y, W);
}
return subtask3(N, M, X, Y, W);
}
