#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
map <pii, int> mp;
const int nmax = 300001;
vector <vector <int> > ff(nmax);
vector <vector <int> > pos(nmax);
vector <vector <ll> > smx(nmax), pmx(nmax);
vector <vector <ll> > pref(nmax);
long long max_weights(int n, int m, vector<int> x, vector<int> y,vector<int> w) {
for(int i = 0; i < m; i++){
x[i]++;
y[i]++;
mp[{x[i], y[i]}] = w[i];
ff[x[i]].pb(y[i]);
}
for(int i= 1; i <= n; i++){
for(int j : ff[i - 1]) pos[i].pb(j);
for(int j : ff[i + 1]) pos[i].pb(j);
for(int j : ff[i]) pos[i].pb(j);
pos[i].pb(-1);
pos[i].pb(n + 1);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
pref[i].resize(pos[i].size());
pref[i][0] = mp[{i, pos[i][0]}];
for(int j = 1; j < pref[i].size(); ++j){
pref[i][j] = pref[i][j - 1] + mp[{i, pos[i][j]}];
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < pos[i].size(); j++)
cout << pos[i][j] << ' ';
cout << "\n";
}
for(int i = 1; i <= n; i++){
vector <ll> dp, DP;
cout << i << "\n";
dp.resize(pos[i].size());
DP.resize(pos[i].size());
smx[i].resize(pos[i].size());
pmx[i].resize(pos[i].size());
if(i == 1){
fill(dp.begin(), dp.end(), 0);
fill(DP.begin(), DP.end(), 0);
}
else{
for(int j = 0; j < pos[i].size(); j++){
int val = pos[i][j];
int u = lower_bound(pos[i - 1].begin(), pos[i - 1].end(), val) - pos[i - 1].begin();
// cout << u << ' ';
dp[j] = smx[i - 1][u] - pref[i][j];
u = upper_bound(pos[i - 1].begin(), pos[i - 1].end(), val) - pos[i - 1].begin();
DP[j] = pmx[i - 1][u - 1] + pref[i - 1][u - 1];
}
// DP[0] = max(dp[0], DP[0]);
// dp.back() = max(DP.back(), dp.back());
DP[0] = max(DP[0], smx[i - 1][0]);
dp.back() = max(dp.back(), pmx[i - 1].back());
}
if(i == n)
return max(dp[0], DP.back());
int o = upper_bound(pos[i + 1].begin(), pos[i + 1].end(), pos[i].back()) -
pos[i + 1].begin() - 1;
smx[i].back() = dp.back() + pref[i + 1][o];
for(int j = pos[i].size() - 2; j >= 0; j--){
int val = pos[i][j];
int o = upper_bound(pos[i + 1].begin(), pos[i + 1].end(), val) - pos[i + 1].begin() - 1;
smx[i][j] = max(smx[i][j + 1], dp[j] + pref[i + 1][o]);
}
pmx[i][0] = DP[0]- pref[i][0];
for(int j = 1; j < pos[i].size(); j++){
pmx[i][j] = max(pmx[i][j - 1], DP[j] - pref[i][j]);
}
}
return 0;
}
