#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int nmax = 1e5 + 5, mmax = 3e5 + 5, inf = 1e15 + 5;
int n, m;
vector<pii> cat[nmax];
class DS {
int l, r, flip;
map<int,int> dp;
void upd(int poz, int x) {
if(dp.empty())
return;
auto it = dp.upper_bound(poz);
if(prev(it) -> second >= x) {
dp[poz] = x;
return;
}
dp[poz] = x;
while(it != dp.end()) {
//cerr << poz << ' ' << x << " VS " << it -> first << ' ' << it -> second << '\n';
if(it -> second <= x)
dp.erase(it);
else
break;
it = dp.upper_bound(poz);
}
return;
}
public:
DS(int x, int val = 0) {
flip = x;
l = n + 1;
r = 2 * n + 1;
dp[l] = val;
}
int get(int poz) {
poz += l;
if(flip) poz = r + l - poz;
if(dp.empty()) return 0;
auto it = dp.upper_bound(poz);
if(it == dp.begin()) {
print();
assert(false); // oh golly gosh gee sper sa nu ma futa chestia asta cand poate debuggez; upd: da
}
return prev(it) -> second;
}
void insert(int poz, int x) {
poz += l;
if(flip) poz = r + l - poz;
upd(poz, x);
}
void push_front(int x) {
l--;
r--;
if(!dp.empty() && dp.rbegin() -> first > r)
dp.erase(dp.rbegin() -> first);
if(dp.empty()) {
dp[l] = x;
return;
}
dp[l] = x - 1;
//cerr << flip << ": ";
//print();
upd(l, x);
}
void print() {
cerr << "> " << l << ' ' << r << '\n';
for(auto [p, x] : dp) {
cerr << p << ' ' << x << '\n';
}
cerr << '\n';
}
};
#undef int
long long max_weights(int N, int M, std::vector<int> x, std::vector<int> y, std::vector<int> cost) { // rezultatul este: Crescendo[N - 2].fin, Descrescendo[N - 1].deb (adica pune stalp inainte de ultima pozitie)
#define int ll
tie(n, m) = pii{N, M};
for(int i = 0; i < m; i++) {
cat[x[i]].emplace_back(y[i], cost[i]);
}
for(int i = 0; i < n; i++)
sort(cat[i].begin(), cat[i].end());
DS cresc(0), decresc(1, -inf);
int mx = 0, lastcresc = 0, lastdecresc = 0;
for(int i = 0; i < n; i++) {
mx = max(lastcresc, mx);
for(auto [h, w] : cat[i])
cresc.insert(h, cresc.get(h) + w);
for(int it = cat[i].size() - 1, h, w; it >= 0; it--) {
tie(h, w) = cat[i][it];
decresc.insert(h, decresc.get(h) + w);
}
//cerr << "<<<<<<<<<<<<<<<<<\n";
//cerr << lastdecresc << ' ' << lastcresc << '\n';
//cresc.print();
//decresc.print();
//cerr << ">>>>>>>>>>>>>>>>>\n";
mx = max(decresc.get(0), mx);
int temp = max(0LL, decresc.get(0));
decresc.push_front(max(lastcresc, lastdecresc));
lastdecresc = max(0LL, temp);
int temp2 = cresc.get(n - 1);
cresc.push_front(max(lastcresc, temp));
lastcresc = temp2;
}
return mx;
}
#undef int
//9 9
//0 0 1
//1 1 2
//2 2 3
//4 0 4
//4 2 5
//6 2 6
//7 1 7
//7 0 8
//8 0 9
//10 10
//0 0 2
//0 9 2
//2 0 2
//2 9 2
//4 0 2
//4 9 2
//6 0 2
//6 9 2
//8 0 2
//8 9 2
