/*
IOI 2022 "Catfish" Solution for Subtask 4 (32%)
Time Complexity: O(N * Y^3)
*/
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
typedef vector <ll> vi;
typedef vector <long long > vl;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
void printVct(vl &v, string s = ""){
cout<<s<<": ";
for (ll i=0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
#define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl;
#define N 100001
#define MAXC 5 // 5 cases
ll n,m;
long long dp[N+1][MAXC+1][MAXC+1];
vector <vii> arr;
vector <vi> s;
void printDP(ll l = 0, ll r = MAXC-1){
for (ll k=l; k<=r; k++){
cout<<"k: "<<k<<endl;
for (ll i = 0; i<n; i++){
cout<<i<<": ";
for (ll j =0; j<MAXC; j++){
cout<<dp[i][j][k];
}
cout<<endl;
}
cout<<endl;
}
cout<<endl;
}
long long calc(ll u, ll l, ll r){
long long sum = 0;
for (ll i=0; i<sz(arr[u]); i++){
if (arr[u][i].F >= l && arr[u][i].F <= r){
sum += arr[u][i].S;
}
}
return sum;
}
long long solve(){
//prep line 0
for (ll j =0; j<MAXC; j++){
for (ll k =0; k<MAXC; k++){
dp[0][j][k] = 0;
}
}
//prep line 1
for (ll j =0; j<MAXC; j++){
for (ll k =0; k<MAXC; k++){
ll new_j = s[1][j], new_k = s[0][k];
if (new_j == new_k) dp[1][j][k] = 0;
else if (new_j > new_k){
dp[1][j][k] = calc(0, new_k+1, new_j);
}
else{
dp[1][j][k] = calc(1, new_j+1, new_k);
}
}
}
// printDP();
//solve
for (ll i =2; i<n; i++){
for (ll j = 0; j<MAXC; j++){
for (ll k =0; k<MAXC; k++){
long long ans = 0, c;
ll new_j = s[i][j], new_k = s[i-1][k], new_y;
if (new_j > new_k){
for (ll y = 0; y<MAXC; y++){
new_y = s[i-2][y];
if (new_y <= new_k){
c = dp[i-1][k][y] + calc(i-1,new_k+1,new_j);
}
else if (new_y < new_j){
c = dp[i-1][k][y] + calc(i-1,new_y+1,new_j);
}
else{
c = dp[i-1][k][y];
}
ans = max(ans, c);
}
}
else{ // j <= k
for (ll y = 0; y<MAXC; y++){
ans = max(ans, dp[i-1][k][y]);
}
if (new_j < new_k){
ans += calc(i, new_j+1, new_k);
}
}
dp[i][j][k] = ans;
}
}
}
// printDP();
long long ans =0;
for (ll i =0; i<n; i++){
for (ll j =0; j<MAXC; j++){
for (ll k =0; k<MAXC; k++){
ans = max(ans, dp[i][j][k]);
}
}
}
return ans;
}
long long max_weights(int NN, int M, vi X, vi Y, vi W) {
n= NN, m =M;
//step 1:
arr.assign(n, vii());
for (ll i=0; i<m; i++){
arr[X[i]].pb(ii(Y[i]+1, W[i]));
}
// for (ll i=0; i<2; i++){
// for (ll j = 0; j<n; j++){
// if (sz(arr[j]) > i) cout<<"("<<arr[j][i].F<<" "<<arr[j][i].S<<"), ";
// else cout<<"(-,-), ";
// }
// cout<<endl;
// }
// cout<<endl;
//step 2:
s.assign(n, vi(5,0));
for (ll i=0; i<n; i++){
ll idx = 0;
if (i != 0){
for (ll j = 0; j<sz(arr[i-1]); j++){
s[i][idx] = arr[i-1][j].F;
idx++;
}
}
if (i != n-1){
for (ll j = 0; j<sz(arr[i+1]); j++){
s[i][idx] = arr[i+1][j].F;
idx++;
}
}
sort(s[i].begin(), s[i].end());
}
// printArr2D(s,n,MAXC,"s");
long long ans = solve();
return ans;
}
