#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>
#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));
#define maxWeights max_weights
const int32_t MAX_N = 1e5;
struct Catfish {
int32_t row;
int32_t id;
mutable int64_t prefSum;
Catfish(int32_t _row, int32_t _id, int32_t w): row(_row), id(_id), prefSum((int64_t) w) {}
bool operator< (const Catfish &other) const {
if(row != other.row) {
return row <= other.row;
}
else {
return id <= other.id;
}
}
};
struct DpState {
int32_t row;
mutable int64_t incrVal, decrVal;
DpState(int32_t _row): row(_row), incrVal(0), decrVal(0) {}
bool operator< (const DpState &other) const {
return row <= other.row;
}
};
int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
std::vector<std::vector<Catfish>> catfishByColumn(n);
for(int32_t i = 0; i < m; i++) {
catfishByColumn[x[i]].push_back(Catfish(y[i], i, w[i]));
}
for(int32_t i = 0; i < n; i++) {
std::sort(catfishByColumn[i].begin(), catfishByColumn[i].end());
int64_t total = 0;
for(auto &x : catfishByColumn[i]) {
total += (int64_t) x.prefSum;
x.prefSum = total;
}
}
std::vector<std::set<DpState>> dp(n + 1);
for(int32_t i = 0; i <= n; i++) {
if(i > 0 && i != n) {
for(auto &x : catfishByColumn[i - 1]) {
dp[i].insert(DpState(x.row + 1));
}
}
if(i < n - 1) {
for(auto &x : catfishByColumn[i + 1]) {
dp[i].insert(DpState(x.row + 1));
}
}
dp[i].insert(DpState(0));
}
auto getWPrefSum = [&](int32_t column, int32_t row) -> int64_t {
if(column >= n) {
return 0;
}
auto p = std::lower_bound(catfishByColumn[column].begin(), catfishByColumn[column].end(), Catfish(row, -1, 0));
if(p == catfishByColumn[column].begin()) {
return 0;
}
p--;
return p->prefSum;
};
for(int32_t i = 1; i <= n; i++) {
{ // compute incrVal
auto prevIt = dp[i - 1].begin();
int64_t pref = 0;
for(auto it = dp[i].begin(); it != dp[i].end(); it++) {
while(prevIt != dp[i - 1].end() && prevIt->row <= it->row) {
remax(pref, prevIt->incrVal - getWPrefSum(i - 1, prevIt->row));
prevIt++;
}
it->incrVal = std::max(pref + getWPrefSum(i - 1, it->row), dp[i - 1].begin()->decrVal);
}
}
{ // compute decrVal
auto prevIt = dp[i - 1].rbegin();
int64_t suff = 0;
for(auto it = dp[i].rbegin(); it != dp[i].rend(); it++) {
while(prevIt != dp[i - 1].rend() && prevIt->row >= it->row) {
remax(suff, std::max(prevIt->incrVal, prevIt->decrVal) + getWPrefSum(i, prevIt->row));
prevIt++;
}
it->decrVal = suff - getWPrefSum(i, it->row);
}
}
}
return std::max(dp.back().begin()->incrVal, dp.back().begin()->decrVal);
}
