#include "fish.h"
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using std::begin;
using std::end;
using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;
template <class T> bool setmax(T& x, const T& y) { return x < y && (x = y, true); }
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<array<int, 2>>> fish(N);
for (int i = 0; i < M; ++i) {
fish[X[i]].push_back({Y[i], W[i]});
}
for (auto& v : fish) {
std::sort(begin(v), end(v));
v.push_back({N, 0});
}
vector<ll> dp0(fish[0].size()), dp1(fish[0].size());
for (int row = 1; row < N; ++row) {
const int n = fish[row - 1].size();
const int m = fish[row].size();
vector<ll> ndp0(m), ndp1(m, *std::max_element(begin(dp0), end(dp0)));
{
vector<ll> acc(m);
for (int i = 0; i < m - 1; ++i) {
acc[i + 1] = acc[i] + fish[row][i][1];
}
int j = n;
ll max = -infll;
for (int i = m - 2; i >= 0; --i) {
while (j > 0 && fish[row - 1][j - 1][0] > fish[row][i][0]) {
j -= 1;
setmax(max, dp0[j] + acc[i + 1]);
}
setmax(ndp0[i], max - acc[i]);
}
}
{
vector<ll> acc(n);
for (int i = 0; i < n - 1; ++i) {
acc[i + 1] = acc[i] + fish[row - 1][i][1];
}
int j = 0;
ll max = -infll;
for (int i = 0; i < m; ++i) {
while (j < n && fish[row - 1][j][0] < fish[row][i][0]) {
setmax(max, dp1[j] - acc[j]);
j += 1;
}
setmax(ndp1[i], max + acc[j]);
}
}
dp0 = std::move(ndp0);
dp1 = std::move(ndp1);
for (int i = 0; i < m; ++i) {
setmax(dp0[i], dp1[i]);
}
}
return *std::max_element(begin(dp0), end(dp0));
}
