#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;
}
}
// subtask 3
{
bool all_y_zero = 1;
for (size_t i = 0; i < m; ++i)
all_y_zero &= !y[i];
if (all_y_zero)
{
vector<int64_t> v(n);
for (size_t i = 0; i < m; ++i)
v[x[i]] = w[i];
vector<array<array<int64_t, 2>, 2>> f(n);
for (size_t i = 1; i < n; ++i)
for (size_t j = 0; j < 2; ++j)
fill(f[i][j].begin(), f[i][j].end(), INT64_MIN / 2);
for (size_t i = 1; i < n; ++i)
{
f[i][0][0] = max(f[i - 1][1][0], f[i - 1][0][0]);
f[i][1][0] = max(f[i - 1][0][1], f[i - 1][1][1]) + v[i];
f[i][0][1] = max(f[i - 1][0][0] + v[i - 1], f[i - 1][1][0]);
f[i][1][1] = max(f[i - 1][0][1], f[i - 1][1][1]);
}
return max(f[n - 1][0][0], max(f[n - 1][0][1], max(f[n - 1][1][0], f[n - 1][1][1])));
}
}
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)
{
// Update s
int64_t h = f[i - 1][0].s;
for (size_t j = 1; j <= n; ++j)
{
f[i][j].s = max(f[i][j].s, h + p[i - 1][j]);
h = max(h, f[i - 1][j].s - p[i - 1][j]);
}
for (size_t j = 0; j <= n; ++j)
{
for (size_t k = j; k <= n; ++k)
f[i][j].s = max(f[i][j].s, f[i - 1][k].z);
}
// Update l
int64_t g = 0; // max f_i-1,k,s f_i-1,k-l + p_ik over all k >= j
for (size_t j = n; j <= n; --j)
{
g = max(g, max(f[i - 1][j].l, f[i - 1][j].s) + p[i][j]);
f[i][j].l = max(f[i][j].l, g - p[i][j]);
}
// Update z
for (size_t j = 0; j <= n; ++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;
}
