#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
using namespace std;
const ll maxn = 3e5 + 5;
ll n, m, ans;
array<ll, 3> a[maxn];
inline void MAX(ll &a, ll b)
{
a = max(a, b);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
n = N;
m = M;
ll sub1 = 1, sub2 = 1, sub3 = 1;
for (ll i = 1; i <= m; i++)
{
// cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][0] = X[i - 1];
a[i][1] = Y[i - 1];
a[i][2] = W[i - 1];
sub1 &= a[i][0] % 2 == 0;
sub2 &= a[i][0] <= 1;
sub3 &= a[i][1] == 0;
}
if (sub1)
{
ll ans = 0;
for (ll i = 1; i <= m; i++)
ans += a[i][2];
return ans;
cout << ans;
} else if (sub2)
{
vector<pair<ll,ll>> val[2];
for (ll i = 1; i <= m; i++)
val[a[i][0]].emplace_back(a[i][1], a[i][2]);
sort(all(val[0]));
sort(all(val[1]));
vector<ll> pf[2];
pf[0].assign(n + 5, 0);
pf[1].assign(n + 5, 0);
for (ll i = 1; i <= val[0].size(); i++)
pf[0][i] = pf[0][i - 1] + val[0][i - 1].second;
for (ll i = 1; i <= val[1].size(); i++)
pf[1][i] = pf[1][i - 1] + val[1][i - 1].second;
ll ans = max(pf[0][val[0].size()], pf[1][val[1].size()]);
for (ll i = 1, pt = -1; i <= val[1].size(); i++)
{
ll height = val[1][i - 1].first - 1;
ll cur = (n > 2 ? pf[1][val[1].size()] - pf[1][i - 1] : 0);
while (pt + 1 < val[0].size() && val[0][pt + 1].first <= height)
pt++;
cur += pf[0][pt + 1];
ans = max(ans, cur);
}
for (ll i = 1, pt = -1; i <= val[0].size(); i++)
{
ll height = val[0][i - 1].first - 1;
ll cur = 0;
while (pt + 1 < val[1].size() && val[1][pt + 1].first <= height)
pt++;
cur += pf[1][pt + 1];
ans = max(ans, cur);
}
return ans;
cout << ans;
} else if (sub3)
{
vector<ll> b(n + 10, 0), dp(n + 10, 0);
for (ll i = 1; i <= m; i++)
b[a[i][0] + 1] = a[i][2];
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
/// choose i
dp[i] = b[i - 1] + b[i + 1];
for (ll j = 3; j <= 50; j++) if (i - j >= 1)
dp[i] = max(dp[i], dp[i - j] + b[i + 1] + b[i - 1]);
else break;
if (i >= 2)
dp[i] = max(dp[i], dp[i - 1] - b[i] + b[i + 1]);
if (i >= 3)
dp[i] = max(dp[i], dp[i - 2] + b[i + 1]);
ans = max(ans, dp[i]);
}
return ans;
cout << ans;
} else
{
vector<vector<ll>> b(n + 10, vector<ll>(n + 10, 0));
ll mx = 0;
for (ll i = 1; i <= m; i++)
b[a[i][0] + 1][a[i][1] + 1] = a[i][2],
mx = max(mx, a[i][1] + 1);
vector<vector<ll>> pf(n + 10, vector<ll>(mx + 2, 0));
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(mx + 1, vector<ll>(mx + 2, 0)));
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= mx; j++)
pf[i][j] = pf[i][j - 1] + b[i][j];
}
for (ll j = 0; j <= mx; j++) for (ll i = 0; i <= mx; i++)
dp[0][i][j] = -1e18;
dp[0][0][0] = 0;
ll be = 0, cu = 1;
for (ll i = 1; i <= n + 2; i++)
{
for (ll u = 0; u <= mx; u++) for (ll v = 0; v <= mx; v++)
dp[cu][u][v] = -1e18;
for (ll pre = 0; pre <= mx; pre++)
for (ll now = 0; now <= mx; now++) if (dp[be][pre][now] != -1e18)
for (ll nxt = 0; nxt <= mx; nxt++)
{
if (now >= nxt)
{
MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i][now] - pf[i][nxt]);
} else
{
if (nxt >= max(pre, now))
MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i - 1][nxt] - pf[i - 1][max(pre, now)]);
}
}
swap(be, cu);
// for (ll u = 0; u <= n; u++) for (ll v = 0; v <= n; v++)
// if (dp[be][u][v] != -1e18)
// cout << i << " " << u << " " << v << " " << dp[be][u][v] << " ?\n";
}
return dp[be][0][0];
cout << dp[be][0][0];
}
}
//signed main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
//// freopen("CATFISH.inp", "r", stdin);
//// freopen("CATFISH.out", "w", stdout);
//
//}
//
