#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
struct Fish {
int x, y, w;
} fish[3 * MAXN];
ll f[303][303][303], maxPre[3003][303], maxSuf[3003][303];
ll dp[3003][3003], sum[3003][3003];
int val[MAXN], nSize, numFish;
ll sub1(void) {
ll sum(0);
for (int i = 0; i < numFish; ++i)
sum += fish[i].w;
return sum;
}
ll sub2(void) {
ll ans(0), sum0(0), sum1(0);
int j(numFish);
for (int i = 0; i < numFish; ++i) {
if(fish[i].x == 0) {
sum0 += fish[i].w;
} else {
if(j == numFish)
j = i;
sum1 += fish[i].w;
}
}
ans = max(sum0, sum1);
if(nSize == 2)
return ans;
sum0 = 0;
for (int i = 0; i < numFish; ++i) {
if(fish[i].x == 1)
break;
sum0 += fish[i].w;
while(j < numFish && fish[j].y <= fish[i].y) {
sum1 -= fish[j].w;
++j;
}
ans = max(ans, sum0 + sum1);
}
return ans;
}
ll sub3(void) {
for (int i = 0; i <= 1; ++i)
dp[i][0] = dp[i][1] = dp[i][2] = -1e18;
for (int i = 0; i < numFish; ++i)
val[fish[i].x] = fish[i].w;
dp[0][2] = 0;
for (int i = 0; i < nSize; ++i) {
int pre(i & 1), cur(!pre);
dp[cur][0] = max(dp[pre][0], max(dp[pre][1], dp[pre][2] + (i > 0 ? val[i - 1] : 0)));
dp[cur][1] = dp[pre][0] + val[i];
dp[cur][2] = max(dp[pre][2], dp[pre][1]);
}
return max({dp[nSize & 1][0], dp[nSize & 1][1], dp[nSize & 1][2]});
}
ll sub5(void) {
for (int i = 0; i < nSize; ++i) {
for (int j = 0; j <= nSize; ++j)
sum[i][j] = 0;
}
for (int i = 0; i < numFish; ++i)
sum[fish[i].x][fish[i].y + 1] += fish[i].w;
for (int i = 0; i < nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] += sum[i][j - 1];
}
for (int j = 0; j <= nSize; ++j) {
for (int k = 0; k <= nSize; ++k) {
f[0][j][k] = -1e18;
}
}
f[0][0][0] = 0;
for (int j = 0; j <= nSize; ++j) {
for (int k = 0; k <= nSize; ++k) {
maxPre[j][k] = f[0][j][k];
if(k > 0)
maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
}
}
for (int j = nSize; j >= 0; --j) {
for (int k = nSize; k >= 0; --k) {
maxSuf[j][k] = f[0][j][k];
if(k + 1 < nSize)
maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
}
}
for (int i = 0; i < nSize; ++i) {
for (int coln = 0; coln <= nSize; ++coln) {
for (int pcol = 0; pcol <= nSize; ++pcol) {
if(coln <= pcol) {
f[i + 1][coln][pcol] = f[i + 1][pcol][0] + sum[i][pcol] - sum[i][coln];
continue;
}
f[i + 1][coln][pcol] = maxPre[pcol][nSize] + (i > 0 ? sum[i - 1][coln] : 0);
}
}
for (int j = 0; j <= nSize; ++j) {
for (int k = 0; k <= nSize; ++k) {
maxPre[j][k] = f[i + 1][j][k] - sum[i][max(j, k)];
if(k > 0)
maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
}
}
for (int j = nSize; j >= 0; --j) {
for (int k = nSize; k >= 0; --k) {
maxSuf[j][k] = f[i + 1][j][k];
if(k < nSize)
maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
}
}
}
ll res(0);
for (int j = 0; j <= nSize; ++j)
res = max(res, maxSuf[j][0]);
return res;
}
/*
ll sub6(void) {
for (int i = 0; i < nSize; ++i) {
for (int j = 0; j <= nSize; ++j)
sum[i][j] = 0;
}
for (int i = 0; i < numFish; ++i)
sum[fish[i].x][fish[i].y + 1] += fish[i].w;
for (int i = 0; i < nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] += sum[i][j - 1];
}
for (int j = 0; j <= nSize; ++j)
dp[0][j] = -1e18;
for (int j = 0; j <= nSize; ++j) {
for (int k = 0; k <= nSize; ++k) {
maxPre[j][k] = f[i + 1][j][k] - sum[i][max(j, k)];
if(k > 0)
maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
}
}
for (int j = nSize; j >= 0; --j) {
for (int k = nSize; k >= 0; --k) {
maxSuf[j][k] = f[i + 1][j][k];
if(k < nSize)
maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
}
}
f[0][0] = 0;
for (int i = 0; i < nSize; ++i) {
for (int coln = 0; coln <= nSize; ++coln) {
f[i + 1][coln] = maxSuf[coln] - sum[i][pcol];
f[i + 1][coln] = max(f[i + 1][coln], maxPre[coln] + (i > 0 ? sum[i - 1][coln] : 0));
}
for (int pcol = 0; pcol <= nSize; ++pcol) {
if(coln <= pcol) {
f[i + 1][coln][pcol] = maxSuf[pcol] + sum[i][pcol] - sum[i][coln];
continue;
}
f[i + 1][coln][pcol] = maxPre[pcol][nSize] + (i > 0 ? sum[i - 1][coln] : 0);
f[i + 1][coln][pcol] = max(f[i + 1][coln][pcol], maxSuf[pcol][0]);
}
}
for (int j = 0; j <= nSize; ++j) {
for (int k = 0; k <= nSize; ++k) {
maxPre[j][k] = f[i + 1][j][k] - sum[i][max(j, k)];
if(k > 0)
maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
}
}
for (int j = nSize; j >= 0; --j) {
for (int k = nSize; k >= 0; --k) {
maxSuf[j][k] = f[i + 1][j][k];
if(k < nSize)
maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
}
}
}
ll res(0);
for (int j = 0; j <= nSize; ++j)
res = max(res, maxSuf[j][0]);
return res;
}
*/
ll max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W) {
nSize = _N, numFish = _M;
bool check1(1), check2(1), check3(1);
for (int i = 0; i < numFish; ++i) {
fish[i] = {_X[i], _Y[i], _W[i]};
check1 &= !(fish[i].x & 1);
check2 &= (fish[i].x <= 1);
check3 &= (fish[i].y == 0);
}
sort(fish, fish + numFish, [](const Fish &a, const Fish &b) {
return (a.x != b.x) ? a.x < b.x : a.y < b.y;
});
if(check1) {
return sub1();
} else
if(check2) {
return sub2();
} else
if(check3) {
return sub3();
} else
if(nSize <= 300) {
return sub5();
} /*else
if(nSize <= 3000) {
return sub6();
}*/
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "fish"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _X, _Y, _W;
int _N, _M;
cin >> _N >> _M;
_X.resize(_N), _Y.resize(_N), _W.resize(_N);
for (int i = 0; i < _N; ++i)
cin >> _X[i] >> _Y[i] >> _W[i];
ll ans = max_weights(_N, _M, _X, _Y, _W);
cout << "ANSWER: " << ans << '\n';
cout << "SUB6: " << sub6() << '\n';
return 0;
}
#endif // Nhoksocqt1
