#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n;
ll dp[maxn][5][5];
vector<pair<int,int>> coin[maxn];
ll cost(int i, int hI, int hB, int hN)
{
int realB = coin[i - 1][hB].first;
int realN = coin[i + 1][hN].first;
ll cost = 0;
for(int j = hI ; j < (int)coin[i].size() ; j++)
if( coin[i][j].first < realB || coin[i][j].first < realN ) cost += coin[i][j].second;
return cost;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
n = N;
for(int i = 0 ; i < M ; i++)
{
X[i]++; Y[i]++;
coin[ X[i] ].push_back( { Y[i] - 1 , W[i] } );
}
coin[0].push_back( { 0 , 0 } );
coin[n + 1].push_back( { 0 , 0 } );
for(int i = 1 ; i <= n ; i++)
{
sort( coin[i].begin() , coin[i].end() );
coin[i].push_back( { n , 0 } );
if( coin[i].front().first != 0 )
coin[i].insert( coin[i].begin() , { 0 , 0 } );
}
for(int hI = 0 ; hI < (int)coin[n].size() ; hI++)
for(int hB = 0 ; hB < (int)coin[n - 1].size() ; hB++)
dp[n][hI][hB] = cost( n , hI , hB , 0 );
for(int i = n - 1 ; i > 0 ; i--)
{
for(int hI = 0 ; hI < (int)coin[i].size() ; hI++)
{
for(int hB = 0 ; hB < (int)coin[i - 1].size() ; hB++)
{
ll& ans = dp[i][hI][hB];
for(int x = 0 ; x < (int)coin[i + 1].size() ; x++)
{
ans = max( ans , dp[i + 1][x][hI] + cost( i , hI , hB , x ) );
}
}
}
}
ll ans = 0;
for(int i = 0 ; i < (int)coin[1].size() ; i++)
ans = max( ans , dp[1][i][0] );
return ans;
}
