#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
using namespace std;
const int maxn = 3e5 + 123;
struct st {
int y = 0;
long long val = 0;
long long pointsBelow = 0;
st() {}
st (int y, long long val, long long pointsBelow) : y(y), val(val), pointsBelow(pointsBelow) {}
bool operator< (const st& ot) const {
return y < ot.y;
}
bool operator< (const int val) const {
return y < val;
}
friend bool operator<(const int& val, const st& ot) {
return val < ot.y;
}
};
vector<st> points[maxn];
vector<long long> prefSum[maxn];
long long getSum(int col, int y) {
if (col < 0) return 0;
long long ans = 0;
int num = upper_bound(points[col].begin(), points[col].end(), y) - points[col].begin();
if (num == points[col].size()) num--;
while (num > -1 && points[col][num].y > y) num--;
if (num == -1) {
return 0;
}
return prefSum[col][num];
}
long long solve(vector<st>& prevRise, vector<st>& prevDown, vector<st>& prevNoPiles, vector<st>& curRise, vector<st>& curDown, vector<st>& curNoPiles, vector<int>& interestingPoints, int curx) {
int prevDownPointer = -1;
int prevRisePointer = -1;
int prevNoPilesPointer = -1;
long long bestDown = 0;
long long bestRise = 0;
long long bestNoPiles = 0;
long long bestNoPilesHigher = 0;
long long overallMax = 0;
for (auto a : prevNoPiles) bestNoPilesHigher = max(bestNoPilesHigher, a.val);
for (int i = 0; i < interestingPoints.size(); i++) {
while (prevRisePointer + 1 < prevRise.size() && prevRise[prevRisePointer + 1].y < interestingPoints[i]) {
prevRisePointer++;
bestDown = max(bestDown, prevRise[prevRisePointer].val - prevRise[prevRisePointer].pointsBelow);
}
while (prevNoPilesPointer + 1 < prevNoPiles.size() && prevNoPiles[prevNoPilesPointer + 1].y <= interestingPoints[i]) {
prevNoPilesPointer++;
bestNoPiles = max(bestNoPiles, prevNoPiles[prevNoPilesPointer].val - prevNoPiles[prevNoPilesPointer].pointsBelow);
}
long long numberOfPoints = 0;
long long numberOfPointsNow = 0;
if (curx) {
numberOfPoints = getSum(curx - 1, interestingPoints[i]);
}
numberOfPointsNow = getSum(curx, interestingPoints[i]);
long long ans = bestNoPilesHigher;
ans = max(ans, numberOfPoints + max(bestDown, bestNoPiles));
curRise.push_back({interestingPoints[i], ans , numberOfPointsNow});
}
prevDownPointer = prevDown.size();
prevRisePointer = prevRise.size();
bestDown = 0;
bestRise = 0;
bestNoPiles = 0;
// << interestingPoints.size() << endl;
for (int i = interestingPoints.size() - 1; i >= 0; i--) {
while (prevRisePointer - 1 >= 0 && prevRise[prevRisePointer - 1].y >= interestingPoints[i]) {
prevRisePointer--;
long long numberOfPointsNowSum = getSum(curx, prevRise[prevRisePointer].y);
bestRise = max(bestRise, prevRise[prevRisePointer].val + numberOfPointsNowSum);
bestNoPiles = max(bestNoPiles, prevRise[prevRisePointer].val);
//if (curx == 4) cout << bestRise << endl;
}
while (prevDownPointer - 1 >= 0 && prevDown[prevDownPointer - 1].y >= interestingPoints[i]) {
prevDownPointer--;
long long numberOfPointsNowSum = getSum(curx, prevDown[prevDownPointer].y);
bestDown = max(bestDown, prevDown[prevDownPointer].val + numberOfPointsNowSum);
bestNoPiles = max(bestNoPiles, prevDown[prevDownPointer].val);
}
long long numberOfPointsNow = getSum(curx, interestingPoints[i]);
long long ans = max(bestDown, bestRise) - numberOfPointsNow;
ans = max(ans, 0ll);
curDown.push_back({interestingPoints[i], ans , numberOfPointsNow});
if (prevDownPointer == prevDown.size() && prevRisePointer == prevRise.size()) ans = 0;
else ans = bestNoPiles + numberOfPointsNow;
curNoPiles.push_back({interestingPoints[i], ans, numberOfPointsNow});
}
reverse(curDown.begin(), curDown.end());
for (auto a : prevDown) overallMax = max(overallMax, a.val);
for (auto a : prevRise) overallMax = max(overallMax, a.val);
for (auto a : prevNoPiles) overallMax = max(overallMax, a.val);
//cout << "OVERALL " << curx << ' ' << curNoPiles[0].val << endl;
curNoPiles.push_back({-1, overallMax, 0});
reverse(curNoPiles.begin(), curNoPiles.end());
return overallMax;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
points[X[i]].push_back(st({Y[i], W[i], 0}));
}
for (int i = 0; i < N; i++) {
sort(points[i].begin(), points[i].end());
for (int j = 0; j < points[i].size(); j++) {
points[i][j].pointsBelow = j;
prefSum[i].push_back(points[i][j].val);
if (j) prefSum[i][j] += prefSum[i][j - 1];
}
}
vector<st> prevRise;
vector<st> prevDown;
vector<st> prevNoPiles;
vector<st> curRise;
vector<st> curDown;
vector<st> curNoPiles;
long long ans = 0;
curNoPiles.push_back({-1, 0, 0});
for (int i = 0; i < N; i++) {
swap(prevRise, curRise);
swap(prevDown, curDown);
swap(prevNoPiles, curNoPiles);
curRise.clear();
curDown.clear();
curNoPiles.clear();
vector<int> interestingPointsUnsorted;
vector<int> interestingPoints;
if (i) {
for (auto a : points[i - 1]) interestingPointsUnsorted.push_back(a.y);
}
for (auto a : points[i]) interestingPointsUnsorted.push_back(a.y);
if (i + 1 < N) {
for (auto a : points[i + 1]) interestingPointsUnsorted.push_back(a.y);
}
sort(interestingPointsUnsorted.begin(), interestingPointsUnsorted.end());
for (int i = 0; i < interestingPointsUnsorted.size(); i++) {
if (i == interestingPointsUnsorted.size() - 1) {
interestingPoints.push_back(interestingPointsUnsorted[i]);
continue;
}
if (interestingPointsUnsorted[i] != interestingPointsUnsorted[i + 1]) {
interestingPoints.push_back(interestingPointsUnsorted[i]);
}
}
ans = max(ans, solve(prevRise, prevDown, prevNoPiles, curRise, curDown, curNoPiles, interestingPoints, i));
}
for (auto a : curDown) {
ans = max(ans, a.val);
}
for (auto a : curRise) {
ans = max(ans, a.val);
}
for (auto a : curNoPiles) {
ans = max(ans, a.val);
}
return ans;
}
/*
void solve() {
int n, m; cin >> n >> m;
vector<int> X, Y, W;
for (int i = 0; i < m; i++) {
int x, y, w; cin >> x >> y >> w;
X.push_back(x);
Y.push_back(y);
W.push_back(w);
}
cout << max_weights(n, m, X, Y, W);
// 5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3]
//cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << endl;
//cout << max_weights(10000, 1, {0}, {0}, {10082010}) << endl;
// cout << max_weights(4, 3, {2, 0, 1}, {2, 0, 1}, {1, 1, 1});
//cout << max_weights(8, 7, {5, 4, 6, 3, 0, 2, 1}, {5, 4, 6, 3, 0, 2, 1}, {1, 1, 1, 1, 1, 1, 1});
// cout << max_weights(5, 3, {1, 2, 3}, {0,0, 0}, {1, 1, 1});
//cout << max_weights(7, 7, {0, 1, 2, 3, 4, 5, 6}, {0, 0, 0, 0, 0, 0, 0}, {1, 2, 3, 4, 5, 6, 7});
}
int main() {
ios_base::sync_with_stdio(0);
solve();
}
*/
