#include "fish.h"
#include <cassert>
#include <deque>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
ll n=N, m=M;
vector a(N, vector<ll>(N));
for (ll i=0; i<m; i++){
a[X[i]][Y[i]]+=W[i];
}
vector dp(N, vector<pair<ll, ll>>(N+1));
for (ll i=1; i<N; i++){
// cout << i << ": " << endl;
deque<pair<ll, ll>> bestU;
pair<ll, ll> mx = {-1, -1};
ll sum=0, rsum=0;
for (ll j=0; j<N; j++) rsum+=a[i][j];
sum=rsum;
for (ll j=N; j>=0; j--){
if (j<N) sum-=a[i][j];
if (max(dp[i-1][j].ff, dp[i-1][j].ss)+sum>mx.ff){
mx = {max(dp[i-1][j].ff, dp[i-1][j].ss)+sum, j};
bestU.push_back(mx);
// cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl;
}
}
sum=0;
for (ll j=0; j<=N; j++){
if (j) sum+=a[i][j-1];
if (bestU.back().ss<j) {
bestU.pop_back();
// cout << "Remove: " << mx.ff << " " << mx.ss << " at " << j << endl;
}
dp[i][j].ss=bestU.back().ff-sum;
}
if (i>1){ //-Change-
pair<ll, ll> best = {-1, -1};
for (ll j=0; j<N+1; j++){
best=max(best, {max(dp[i-2][j].ff, dp[i-2][j].ss), j});
}
ll osum=0;
for (ll j=0; j<best.ss; j++){
osum+=a[i-1][j];
}
sum=0;
for (ll j=0; j<=best.ss; j++){
if (j) sum+=a[i-1][j-1];
dp[i][j].ff=best.ff+max(sum, osum);
}
}
assert(bestU.size()<=1);
while (!bestU.empty()) bestU.pop_back();
mx = {-1, -1};
sum=rsum=0;
for (ll j=0; j<N; j++) rsum+=a[i-1][j];
for (ll j=0; j<=N; j++){
if (j) sum+=a[i-1][j-1];
if (rsum-sum+dp[i-1][j].ff>mx.ff){
mx = {rsum-sum+dp[i-1][j].ff, j};
bestU.push_back(mx);
}
}
sum=0;
for (ll j=N; j>=0; j--){
if (j<N) sum+=a[i-1][j];
if (bestU.back().ss>j) bestU.pop_back();
dp[i][j].ff=max(dp[i][j].ff, bestU.back().ff-sum);
}
}
// for (ll i=N; i>=0; i--){
// for (ll j=0; j<N; j++) cout << dp[j][i].ff << " ";
// cout << endl;
// }
// for (ll i=N; i>=0; i--){
// for (ll j=0; j<N; j++) cout << dp[j][i].ss << " ";
// cout << endl;
// }
ll res=0;
for (ll i=0; i<=n; i++){
res=max(res, max(dp[n-1][i].ff,dp[n-1][i].ss));
}
return res;
}
