#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
long long max_weights(int numCol, int numCatfish, vector <int> cols, vector <int> rows, vector <int> weights) {
vector <vector <pair <int, long long>>> atCol(numCol);
REP(i, numCatfish) {
atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
}
REP(i, numCol) {
sort(ALL(atCol[i]));
atCol[i].emplace_back(numCol, 0);
long long pre = 0;
for (auto &[_, x] : atCol[i]) {
x += pre;
pre = x;
}
}
auto prefix_sum = [&] (int i, int cur) -> long long {
assert(0 <= i && i < numCol);
auto it = lower_bound(ALL(atCol[i]), make_pair(cur, -1ll));
if(it != atCol[i].begin()) return prev(it) -> second;
return 0;
};
vector <vector <vector <long long>>> dp(numCol, vector <vector <long long>>(2));
REP(i, numCol) {
dp[i][0].resize((int) atCol[i].size(), 0);
dp[i][1].resize((int) atCol[i].size(), 0);
long long Max = 0;
if(i == 0) continue;
for (int cur = (int) atCol[i].size() - 1, pre = (int) atCol[i - 1].size(); cur >= 0; cur--) {
while(pre > 0 && atCol[i - 1][pre - 1].first >= atCol[i][cur].first) {
pre--;
maximize(Max, max(dp[i - 1][0][pre], dp[i - 1][1][pre]) + prefix_sum(i, atCol[i - 1][pre].first));
}
maximize(dp[i][0][cur], Max - prefix_sum(i, atCol[i][cur].first));
// cout << i << " 0 " << atCol[i][cur].first << " " << Max << '\n';
}
Max = (i > 1 ? max(*max_element(ALL(dp[i - 2][0])), *max_element(ALL(dp[i - 2][1]))) : 0);
for (int cur = 0, pre = -1; cur < (int) atCol[i].size(); ++cur) {
while(pre + 1 < (int) atCol[i - 1].size() && atCol[i - 1][pre + 1].first <= atCol[i][cur].first) {
pre++;
maximize(Max, dp[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].first));
}
// cout << cur << '\n';
maximize(dp[i][1][cur], Max + prefix_sum(i - 1, atCol[i][cur].first));
// cout << i << " 0 " << atCol[i][cur].first << " " << dp[i][1][cur] << '\n';
}
}
return max(*max_element(ALL(dp[numCol - 1][0])), *max_element(ALL(dp[numCol - 1][1])));
}
