#include "fish.h"
#include <cstdio>
#include <vector> 
#include <algorithm>
#include <cstring>

#define X first
#define Y second
#define PB push_back
#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 19;
const int N = 1 << LOG;

int n, m;
int xc[N], yc[N], weg[N];

vector<int> fsh[N];

auto comp01 = [](const int &a, const int &b) { 
	return yc[a] < yc[b] || (yc[a] == yc[b] && xc[a] < xc[b]);
};

auto comp10 = [](const int &a, const int &b) { 
	return yc[a] < yc[b] || (yc[a] == yc[b] && xc[a] > xc[b]);
};

int mid;
bool comp102(int a, int b) { 
	return yc[a] < yc[b] || (yc[a] == yc[b] && xc[a] == mid);
}

ll tour[2 * N], prop[2 * N];

void clear(int siz) { 
	for(int i = 0; i < siz; ++i) {
		for(int u = i + N; u; u >>= 1) { 
			tour[u] = prop[u] = 0;
		}
	}
}

void propagate(int u) { 
	tour[2 * u] += prop[u];
	prop[2 * u] += prop[u];
	tour[2 * u + 1] += prop[u];
	prop[2 * u + 1] += prop[u];
	prop[u] = 0;
}

void update(int l, int r, ll w, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return; }
	if(l <= lo && hi <= r) { 
		tour[u] += w;
		prop[u] += w;
		return; 
	}
	int mi = (lo + hi) / 2;
	propagate(u);
	update(l, r, w, 2 * u, lo, mi);
	update(l, r, w, 2 * u + 1, mi, hi);
	tour[u] = max(tour[2 * u], tour[2 * u + 1]);
}

ll max_all, dp[N], maxa[N];
vector<int> sweep;

int lb(int h, int x) { 
	int lo = 0, hi = fsh[x].size();
	for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
		if(yc[fsh[x][mi]] < h) { 
			lo = mi;
		} else {
			hi = mi;
		}
	}
	return hi;
}

int ub(int h, int x) { 
	int lo = 0, hi = fsh[x].size();
	for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
		if(yc[fsh[x][mi]] <= h) { 
			lo = mi;
		} else {
			hi = mi;
		}
	}
	return hi;
}

ll max_weights(int nn, int mm, vector<int> X, vector<int> Y, vector<int> W) {
	n = nn;
	m = mm;
	for(int i = 0; i < m; ++i) { 
		xc[i] = X[i] + 1;
		yc[i] = Y[i] + 1;
		weg[i] = W[i];

		fsh[xc[i]].PB(i);
	}

	fsh[0].PB(m);
	yc[m] = 0;
	xc[m] = 0;
	for(int i = 1; i <= n; ++i) { 
		fsh[i].PB(m + i);
		yc[m + i] = n + 1;
		xc[m + i] = i;

		sort(fsh[i].begin(), fsh[i].end(), comp01);
		debug("%d: ", i);
		for(int x : fsh[i]) { debug("%d ", x); }
		debug("\n");
	}

	for(int i = n; i >= 0; --i) {
		int one = fsh[i + 1].size(), two = fsh[i + 2].size();
		// 1
		sweep.clear();
		for(int j = 0; j < one; ++j) { 
			update(j, j + 1, dp[fsh[i + 1][j]]);
			sweep.PB(fsh[i + 1][j]);
		}

		for(int f : fsh[i]) { 
			sweep.PB(f);
		}

		sort(sweep.begin(), sweep.end(), comp01);

		for(int f : sweep) { 
			if(xc[f] == i) { 
				dp[f] = tour[1];
			} else {
				update(0, ub(yc[f], i + 1), weg[f]);
			}
		}
		clear(one);

		//2
		sweep.clear();
		for(int j = 0; j < two; ++j) { 
			update(j, j + 1, dp[fsh[i + 2][j]]);
		}

		for(int f : fsh[i + 1]) { 
			update(ub(yc[f], i + 2), two, weg[f]);
			sweep.PB(f);
		}

		for(int f : fsh[i]) {
			sweep.PB(f);
		}

		sort(sweep.begin(), sweep.end(), comp01);
		for(int f : sweep) { 
			if(xc[f] == i) { 
				dp[f] = max(dp[f], tour[1]);
			} else {
				update(0, ub(yc[f], i + 2), weg[f]);
			}
		}
		clear(two);

		//3

		max_all = max(max_all, maxa[i + 3]);
		sweep.clear();
		for(int f : fsh[i]) { 
			sweep.PB(f);
		} 
		for(int f : fsh[i + 1]) {
			sweep.PB(f);
		}

		sort(sweep.begin(), sweep.end(), comp01);
		ll prf = 0;
		for(int f : sweep) { 
			if(xc[f] == i) { 
				dp[f] = max(dp[f], max_all + prf);
			} else {
				prf += weg[f];
			}
		}

		// maxall

		sweep.clear();
		for(int f : fsh[i]) { 
			sweep.PB(f);
		} 
		if(i) { 
			for(int f : fsh[i - 1]) {
				sweep.PB(f);
			}
		}

		sort(sweep.begin(), sweep.end(), comp10);
		prf = 0;
		for(int f : sweep) { 
			if(xc[f] == i) { 
				maxa[i] = max(maxa[i], dp[f] + prf);
				debug("%d (%d, %d) %lld %lld\n", f, xc[f], yc[f], dp[f], prf);
			} else { 
				prf += weg[f];
			}
		}
	}

	return dp[m];
}