#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<long long> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
long long max(long long x, long long y){
if (x > y) return x;
else return y;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int, int>>> o(N+1);
FOR(i,0,M){
o[X[i]].pb({Y[i], W[i]});
}
FOR(i,0,N) sort(all(o[i]));
FOR(i,0,N){
int t = o[i].size();
if (t > 0){
if (o[i][0].first != 0){
o[i].pb({0,0});
}
if (o[i][t-1].first != N-1){
o[i].pb({N-1, 0});
}
}
}
vector<long long> prefix1(N+1);
vector<long long> dp1(N+1);
vector<long long> prefix2(N+1);
vector<long long> dp2(N+1);
for (auto x: o[0]) prefix1[x.first] += x.second;
FOR(i,1,N) prefix1[i] += prefix1[i-1];
long long answer = 0;
// printVector(prefix1);
FOR(i,1,N){
for (auto x: o[i]) prefix2[x.first] += x.second;
FOR(j,1,N) prefix2[i] += prefix2[i-1];
vector<pair<int, int>> e;
for (auto x: o[i-1]) e.pb({x.first, 0});
for (auto x: o[i]) e.pb({x.first, -1});
sort(all(e));
int c = 0ll;
for (auto item: e){
// if (item.second == 0){
c = max(c, dp1[item.first]-prefix1[item.first]);
// }else{
dp2[item.first] = max(dp2[item.first], prefix1[item.first]+c);
// }
}
int d = 0ll;
reverse(all(e));
for (auto item: e){
// if (item.second == 0){
d = max(d, dp1[item.first]+prefix2[item.first]);
// }else{
dp2[item.first] = max(dp2[item.first], -prefix2[item.first]+d);
// }
}
FOR(i,1,N) answer = max(answer, dp2[i]);
// printVector(dp2);
swap(prefix1, prefix2);
swap(dp1, dp2);
dp2.clear();
prefix2.clear();
dp2.resize(N);
prefix2.resize(N);
}
return answer;
}
