#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define pv(x) {}
#endif
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
/// pier optimal options are below each fish in each column or full column
/// dp[i][j][k], I am at column i with the following status:
/// at column (i-1) the pier was built below fish j and above that the fish caught were k
int i,j,k;
vector<vector<pi> > col(n,vector<pi>());
//p(1)
for(i=0;i<m;i++){
col[x[i]].push_back({y[i],w[i]});
}
for(i=0;i<n;i++){
sort(all(col[i]));
}
vector<vector<vector<ll> > > dp(n,vector<vector<ll> >());
vector<vector<ll> > best(n,vector<ll>()),eaten(n,vector<ll>());
vector<ll> ans(n,-INF);
//p(2)
for(i=0;i<n;i++){
//p(i)
int sz = col[i].size();
dp[i].assign(sz+1,vector<ll>());
best[i].assign(sz+1,-INF);
eaten[i].assign(sz+1,-INF);
for(j=0;j<=sz;j++){
dp[i][j].assign(sz+1-j,-INF);
}
}
/// starting at i = 0 (base case)
int sz = col[0].size();
//p(3)
ans[0] = 0;
for(j=0;j<=sz;j++){
dp[0][j][0] = 0;
best[0][j] = 0;
eaten[0][j] = 0;
}
//p(4)
p("go")
for(i=1;i<n;i++){
/// at column i with sz fish
int sz = col[i].size();
int sz1 = col[i-1].size();
ll tot = 0;
int p1 = 0;
ans[i] = max(ans[i],ans[i-1]);
for(j=0;j<sz;j++){
p(j)
int h = col[i][j].F-1;
/// build pier up to h
/// 2 cases:
/// (i-1) catches my fish
int idx = j;
ll sum = 0;
best[i][j] = max(best[i][j],ans[i-1]);
eaten[i][j] = max(eaten[i][j],ans[i-1]);
for(k=0;k<sz1;k++){
while(idx < sz && col[i][idx].F <= col[i-1][k].F-1){
sum += col[i][idx].S;
idx++;
}
ll temp = best[i-1][k] + sum;
//p(temp)
best[i][j] = max(best[i][j],temp);
eaten[i][idx] = max(eaten[i][idx],temp);
ans[i] = max(ans[i],temp);
}
/// case of full col
while(idx < sz){
sum += col[i][idx].S;
idx++;
}
ll temp = best[i-1][k] + sum;
best[i][j] = max(best[i][j],temp);
eaten[i][idx] = max(eaten[i][idx],temp);
ans[i] = max(ans[i],temp);
/// I catch fish from (i-1)
while(p1 < sz1 && col[i-1][p1].F <= h){
tot += col[i-1][p1].S;
p1++;
}
// I can get up to fish (p1-1)
ll temp2 = tot;
//p(j)
for(k=0;k<p1;k++){
/// I will get fish from {k,p1-1} (temp)
/// i need best dp[i-1][o][oo] with o+oo == k
//p(k)
//p(temp2)
ll temp = eaten[i-1][k] + temp2;
//p(temp)
best[i][j] = max(best[i][j],temp);
eaten[i][j] = max(eaten[i][j],temp);
ans[i] = max(ans[i],temp);
temp2 -= col[i-1][k].S;
}
}
/// case of full col
/// build pier up to h
best[i][j] = max(best[i][j],ans[i-1]);
eaten[i][j] = max(eaten[i][j],ans[i-1]);
/// 2 cases
/// I catch fish from (i-1)
while(p1 < sz1){
tot += col[i-1][p1].S;
p1++;
}
// I can get up to fish (p1-1)
ll temp2 = tot;
//p(temp2)
//p(p1)
for(k=0;k<p1;k++){
/// I will get fish from {k,p1-1} (temp)
/// i need best dp[i-1][o][oo] with o+oo == k
ll temp = eaten[i-1][k] + temp2;
//p(temp)
best[i][j] = max(best[i][j],temp);
eaten[i][j] = max(eaten[i][j],temp);
ans[i] = max(ans[i],temp);
temp2 -= col[i-1][k].S;
}
pv(best[i])
pv(eaten[i])
}
// from last col
pv(ans)
return ans[n-1];
}
