#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
map<int, ll> v[N], h[N];
vector<ll> f[N];
vector<int> pos[N];
vector<pair<int, ll>> S[N];
ll s(int p, int u) {
  if (auto it = lower_bound(S[p].begin(), S[p].end(), pair(u + 1, (ll) -1e18)); it != S[p].begin()) return prev(it)->second;
  return 0;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  for (int i = 0; i < m; ++i)
    v[x[i] + 1][y[i] + 1] += w[i], pos[x[i] + 1].push_back(y[i]); 
  for (int i = 1; i <= n; ++i) {
    sort(pos[i].begin(), pos[i].end()), pos[i].push_back(n);
    ll c = 0;
    for (auto [p, v]: v[i])
      c += v, S[i].emplace_back(p, c);
  }
  for (int j: pos[1])
    h[1][j] = 0;
  f[1].resize(pos[1].size());
  for (int i = 2; i <= n; ++i) {
    f[i].resize(pos[i].size());
    auto g = pos[i - 1].size() - 1;
    ll ma = -1e18;
    for (int j = (int) pos[i].size() - 1; j >= 0; --j) {
      while (~g && pos[i - 1][g] >= pos[i][j])
        ma = max(ma, f[i - 1][g] + s(i, pos[i - 1][g])), --g;
      f[i][j] = ma - s(i, pos[i][j]);
    }
    auto l = h[i - 1].begin();
    ma = -1e18;
    for (int j = 0; j < pos[i].size(); ++j) {
      while (l != h[i - 1].end() && l->first <= pos[i][j])
        ma = max(ma, l->second - s(i - 1, l->first)), ++l;
      f[i][j] = max(f[i][j], h[i][pos[i][j]] = ma + s(i - 1, pos[i][j]));
    }
    for (int j = 0; j < pos[i - 1].size(); ++j)
      h[i][pos[i - 1][j]] = max(h[i][pos[i - 1][j]], f[i - 1][j] + s(i, pos[i - 1][j]));
  }
  ll mx = 0;
  for (ll v: f[n])
    mx = max(mx, v);
  return mx;
}

answer.code: In function ‘ll s(int, int)’:
answer.code:11:7: warning: init-statement in selection statements only available with ‘-std=c++17’ or ‘-std=gnu++17’
   11 |   if (auto it = lower_bound(S[p].begin(), S[p].end(), pair(u + 1, (ll) -1e18)); it != S[p].begin()) return prev(it)->second;
      |       ^~~~
answer.code:11:59: error: missing template arguments before ‘(’ token
   11 |   if (auto it = lower_bound(S[p].begin(), S[p].end(), pair(u + 1, (ll) -1e18)); it != S[p].begin()) return prev(it)->second;
      |                                                           ^
answer.code: In function ‘ll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)’:
answer.code:20:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   20 |     for (auto [p, v]: v[i])
      |               ^