#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const int mxN2 = (int)3e2+10;
const ll LINF = (ll)2e18;
int n, m;
struct Fish{ int x, y, w; };
vector<Fish> fishes;
ll dp[mxN][10][10];
ll pref[mxN][4];
int mxY = 2;

ll max_weights(int N, int M, vi _X, vi _Y, vi _W) {
	n = N, m = M; mxY=min(mxY,N);
	for(int i = 0; i < m; i++) 
		fishes.pb({_X[i]+1,_Y[i]+1,_W[i]});
	sort(all(fishes),[&](Fish a, Fish b){
		if(a.x!=b.x) return a.x<b.x;
		return a.y<b.y;
	});
	for(int i = 0; i < m; i++){
		auto [x,y,w] = fishes[i];
		pref[x][y]+=w;
	}
	for(int i = 0; i <= n; i++)
		for(int j = 1; j <= 2; j++)
			pref[i][j]+=pref[i][j-1];
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= mxY; j++)
			for(int k = 0; k <= mxY; k++)
				dp[i][j][k]=-LINF;
	ll ans = 0;
	for(int i = 0; i <= mxY; i++){
		for(int j = 0; j <= mxY; j++){
			if(i>j) dp[2][i][j]=pref[1][i]-pref[1][j];
			else if(i<j) dp[2][i][j]=pref[2][j]-pref[2][i];
			else dp[2][i][j]=0;
			ans=max(ans, dp[2][i][j]+pref[3][i]);
		}
	}
	for(int i = 3; i <= n; i++){
		for(int j = 0; j <= mxY; j++){
			for(int k = 0; k <= mxY; k++){
				ll costi = 0;
				if(k>j) costi=pref[i][k]-pref[i][j];
				for(int l = 0; l <= k; l++){
					ll costi1 = 0;
					if(j>k) costi1 = pref[i-1][j]-pref[i-1][k];
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+costi1);
				}
				for(int l = k+1; l<= mxY; l++){
					ll costi1 = 0;
					if(j>l) costi1 = pref[i-1][j]-pref[i-1][l];
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+costi1);
				}
				dp[i][j][k]+=costi;
				ans = max(ans, dp[i][j][k]+pref[i+1][j]);
			}
		}
	}
	return ans;
}