#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
using arr = array<ll, 2>;
constexpr int maxn = 1e5 + 5, maxm = 3e5;
int n, m;
constexpr int maxh = 11;
vector <arr> fish[maxn];
ll dp[maxn][maxh][maxh] = { 0 }; // Pos, pos - 2 column, pos - 1 column
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
n = N, m = M;
for (int &i: X) i++;
for (int &i : Y) i++;
for (int i = 0; i < maxn; i++) fish[i].push_back({0, 0});
for (int i = 0; i < m; i++)
{
fish[X[i]].push_back(arr{Y[i], W[i]});
}
for (int i = 0; i < n; i++) sort(fish[i].begin(), fish[i].end());
for (int i = 1; i <= n; i++) {
// cout << "x: " << i << "\t";
for (int y = 1; y < (int)fish[i].size(); y++)
{
fish[i][y][1] += fish[i][y - 1][1];
// cout << fish[i][y][1] << " ";
}
// cout << "\n";
}
// cout << "\n\n\n";
int h = maxh;
h = min(n + 1, h);
// Making the starting column start in the right place
for (int x = 2; x <= n; x++)
{
// cout << "x: " << x << "\n";
for (int s = 0; s < h; s++) // Our new arm
{
// cout << "s: " << s << "\t";
for (int f = 0; f < h; f++) // Older arms
{
// dp[x][s][f] = max(dp[x - 1][f][y] + fish in column pos - 1 caught)
for (int y = 0; y < h; y++)
{
dp[x][s][f] = max(dp[x][s][f], dp[x - 1][f][y] +
(*(upper_bound(fish[x - 1].begin(), fish[x - 1].end(), arr{max(s, y) + 1, -1}) - 1))[1] -
(*(upper_bound(fish[x - 1].begin(), fish[x - 1].end(), arr{min(f, max(s, y)) + 1, -1}) - 1))[1]);
if (x == 2) break;
}
// cout << dp[x][s][f] << " ";
}
// cout << "\n";
}
// cout << "\n\n";
}
ll output = 0;
for (int s = 0; s < n; s++) for (int f = 0; f < n; f++) output = max(output, dp[n][s][f]);
return output;
}
