#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
auto n = N, m = M;
auto x = X, y = Y, w = W;
if(n == 1)
return 0;
if(n == 2)
{
ll f = 0, s = 0;
for(int i = 0; i < m; i++)
{
if(x[i] == 0)
f += w[i];
else
s += w[i];
}
return max(f, s);
}
for (auto &i : y)
i = n - i - 1;
vector<int> cc;
for (int i = 0; i < m; i++)
cc.push_back(y[i]);
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (auto &i : y)
i = lower_bound(cc.begin(), cc.end(), i) - cc.begin();
int k = cc.size();
vector<ll> pref0(k), pref1(k);
for(int i = 0; i < m; i++)
{
if(x[i] == 0)
pref0[y[i]] = w[i];
else
pref1[y[i]] = w[i];
}
for(int i = 1; i < k; i++)
pref0[i] += pref0[i - 1], pref1[i] += pref1[i - 1];
ll mx = pref1.back();
for(int i = 0; i < k; i++)
{
ll curr = pref1.back() - pref1[i] + pref0[i];
mx = max(mx, curr);
}
return mx;
}
