#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 3001;
struct state
{
int64_t s, l, z;
};
state f[N][N];
int64_t p[N][N];
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
// subtask 1
{
bool all_even = 1;
for (size_t i = 0; i < m; ++i)
all_even &= !(x[i] & 1);
if (all_even)
{
int64_t sum = 0;
for (size_t i = 0; i < m; ++i)
sum += w[i];
return sum;
}
}
// subtask 2
{
bool leq1 = 1;
for (size_t i = 0; i < m; ++i)
leq1 &= x[i] <= 1;
if (leq1)
{
int64_t z = 0, t = 0;
vector<pair<int, int>> zero, one;
for (size_t i = 0; i < m; ++i)
if (x[i])
one.emplace_back(y[i], w[i]), z += w[i];
else
zero.emplace_back(y[i], w[i]), t += w[i];
if (n == 2)
return max(t, z);
sort(one.begin(), one.end());
sort(zero.begin(), zero.end());
int64_t ans = z;
auto it = zero.begin(), jt = one.begin();
for (int i = 0; i <= n && (it != zero.end() || jt != one.end()); ++i)
{
if (it != zero.end() && it->first < i)
z += it->second, ++it;
if (jt != one.end() && jt->first < i)
z -= jt->second, ++jt;
ans = max(ans, z);
}
return ans;
}
}
for (size_t i = 1; i < n; ++i)
for (size_t j = 0; j < n; ++j)
f[i][j].s = f[i][j].l = f[i][j].z = INT64_MIN / 2;
for (size_t i = 0; i < m; ++i)
p[x[i]][y[i] + 1] = w[i];
for (size_t i = 0; i < n; ++i)
for (size_t j = 1; j <= n; ++j)
p[i][j] += p[i][j - 1];
for (size_t i = 1; i < n; ++i)
for (size_t j = 0; j <= n; ++j)
{
for (size_t k = 0; k < j; ++k)
f[i][j].s = max(f[i][j].s, p[i - 1][j] - p[i - 1][k] + max(f[i - 1][k].s, f[i - 1][k].z));
for (size_t k = j; k <= n; ++k)
f[i][j].s = max(f[i][j].s, f[i - 1][k].z);
for (size_t k = j; k <= n; ++k)
f[i][j].l = max(f[i][j].l, max(f[i - 1][k].l, f[i - 1][k].s) + p[i][k] - p[i][j]);
f[i][j].z = max(f[i - 1][j].s, f[i - 1][j].l) + p[i][j];
if (!j)
{
for (size_t k = 0; k <= n; ++k)
f[i][j].z = max(f[i][j].z, f[i - 1][k].z);
}
}
int64_t ans = 0;
for (size_t j = 0; j <= n; ++j)
ans = max(ans, max(f[n - 1][j].s, max(f[n - 1][j].l, f[n - 1][j].z)));
return ans;
}
