#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#include<unordered_map>
#pragma GCC optimize(3)
typedef long long int ll;
using namespace std;
long long int a[2][300005];
long long int mp[100005][10];
long long int dp[100005][10][10];
long long int s[100005][10];
vector<int> row[300005];
vector<pair<int,int> > vv[300005];
int find(int coll,int high)
{
int pe = 0;
for(int i=0;i<vv[coll].size();i++)
{
if(high >= vv[coll][i].first) pe += vv[coll][i].second;
}
return pe;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
//subtask1:
bool flag1 = true;
for(int i=0;i<X.size();i++)if(X[i] %2 != 0)flag1 = false;
if(flag1 == true)
{
long long int su = 0;
for(int i=0;i<W.size();i++)su += W[i];
return su;
}
//
//subtask2:
bool flag2 = true;
for(int i=0;i<X.size();i++)if(X[i] > 1)flag2 = false;
if(flag2 == true)
{
long long int maxn = -1;
long long int su = 0;
for(int i=0;i<X.size();i++)a[X[i]][Y[i]] = W[i];
if(N > 2)
{
for(int i=0;i<N;i++)su += a[1][i];
maxn = max(maxn,su);
for(int i=0;i<N;i++)
{
su -= a[1][i];
su += a[0][i];
maxn = max(maxn,su);
}
return maxn;
}
else
{
long long int su1 = 0;
long long int su2 = 0;
for(int i=0;i<N;i++)su1 += a[0][i];
for(int i=0;i<N;i++)su2 += a[1][i];
return max(su1,su2);
}
}
for(int i=0;i<X.size();i++)X[i] += 1;
for(int i=0;i<Y.size();i++)Y[i] += 1;
//subtask3:
bool flag34 = true;
for(int i=0;i<M;i++)
{
if(Y[i] > 10)flag34 = false;
}
long long int zero = 0;
if(flag34 == true)
{
for(int i=0;i<M;i++)mp[X[i]][Y[i]] = W[i];
for(int i=1;i<=N;i++)
{
for(int j=1;j<=9;j++)s[i][j] = s[i][j-1] + mp[i][j];
}
long long int maxn = -1;
for(int i=1;i<=N;i++)
{
for(int j=0;j<=min(N,9);j++)
{
for(int k=0;k<=min(N,9);k++)
{
for(int l=0;l<=min(N,9);l++)
{
if(i!=1)dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(s[i][max(k,l)] - s[i][j],zero));
else dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(s[i][l] - s[i][j],zero));
}
}
}
if(i!=1)
{
for(int j=0;j<=min(N,9);j++)
{
for(int k=0;k<=min(N,9);k++)
{
for(int pp=0;pp<=min(N,9);pp++)
{
dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][pp] + max(s[i][k] - s[i][j],zero));
}
}
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=0;j<=min(N,9);j++)
{
for(int k=0;k<=min(N,9);k++)
{
maxn = max(maxn,dp[i][j][k]);
}
}
}
return maxn;
}
else
{
for(int i=0;i<X.size();i++)vv[X[i]].push_back(make_pair(Y[i],W[i]));
for(int i=0;i<X.size();i++)
{
row[X[i]-1].push_back(Y[i]);
row[X[i]+1].push_back(Y[i]);
}
for(int i=1;i<=N;i++)
{
row[i].push_back(0);
sort(row[i].begin(),row[i].end());
sort(vv[i].begin(),vv[i].end());
}
for(int i=1;i<=N;i++)
{
for(int j=0;j<row[i].size();j++)
{
for(int k=0;k<row[i-1].size();k++)
{
for(int l=0;l<row[i+1].size();l++)
{
int maxcol = row[i+1][l];
if(i!=1)maxcol = max(row[i-1][k],maxcol);
int del = find(i,row[i][j]);
int ad = find(i,maxcol);
dp[i+1][l][j] = max(dp[i+1][l][j],dp[i][j][k] + max(ad-del,0));
}
}
}
if(i!=1)
{
for(int j=0;j<row[i].size();j++)
{
for(int k=0;k<row[i-1].size();k++)
{
for(int p=0;p<row[i-2].size();p++)
{
int ad = find(i,row[i-1][k]);
int del = find(i,row[i][j]);
dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][p] + max(ad-del,0));
}
}
}
}
}
long long int maxn = -1;
for(int i=1;i<=N;i++)
{
for(int j=0;j<row[i].size();j++)
{
for(int k=0;k<row[i-1].size();k++)
{
maxn = max(maxn,dp[i][j][k]);
}
}
}
return maxn;
}
//
return 0;
}
