#include "fish.h"
#include<bits/stdc++.h>
#include <vector>
#pragma GCC optimize("O3")
#define ll long long
using namespace std;
const int N = 3010;
const int LOGN = 12;
struct RMQ{
ll pref[N], suf[N];
int n;
void build(vector <ll> &v){
n = v.size();
pref[0] = -1e18;
for(int i = 1;i <= n;i++){
pref[i] = max(pref[i-1], v[i-1]);
}
suf[n+1] = -1e18;
for(int i = n;i > 0;i--){
suf[i] = max(suf[i+1], v[i-1]);
}
return;
}
ll query(int l, int r){
l++;
r++;
if(l > r) return -1e18;
if(l == 0) return pref[r];
return suf[l];
}
} rmq[2];
ll dp[N][N][4];
vector <pair <int, ll>> x[N];
int n, m;
ll pref[N][2];
long long max_weights(int NN, int MM, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n = NN;
m = MM;
for(int i = 0;i < m;i++){
x[X[i]+1].push_back({Y[i]+1, W[i]});
}
for(int i = 0;i < N;i++){
sort(x[i].begin(), x[i].end());
}
for(int i = 1;i <= n;i++){
//cout << i << '\n';
vector <ll> ant;
for(int j = 1, l = 0;j <= n;j++){
pref[j][0] = pref[j-1][0];
if(l != x[i].size()){
if(x[i][l].first == j){
pref[j][0] += x[i][l].second;
l++;
}
}
}
for(int j = 1, l = 0;j <= n;j++){
pref[j][1] = pref[j-1][1];
if(l != x[i+1].size()){
if(x[i+1][l].first == j){
pref[j][1] += x[i+1][l].second;
l++;
}
}
}
for(int y = 0;y <= n;y++){
ant.push_back(dp[i-1][y][1]-pref[y][0]);
//if(i == 3) //cout << ant.back() << ' ';
}
//if(i == 3) //cout << '\n';
//// //cout << '\n';
rmq[0].build(ant);
ant.clear();
for(int y = 0;y <= n;y++){
ant.push_back(max({dp[i-1][y][0]+pref[y][1]}));
// //cout << pref[y][1] << ' ';
}
// //cout << '\n';
rmq[1].build(ant);
// //cout << rmq[1].query(1, n) << ' ' << rmq[1].query(2, n) << '\n';
// //cout << pref[0][1] << ' ' << pref[1][1] << '\n';
for(int y = 0;y <= n;y++){
dp[i][y][0] = max({rmq[0].query(0, y)+pref[y][0], rmq[1].query(y+1, n)-pref[y][1], dp[i-1][y][2] + pref[y][0], dp[i-1][y][3] + pref[y][0]});
//cout << dp[i][y][0] << ' ';
}
//cout << '\n';
ant.clear();
for(int y = 0;y <= n;y++){
ant.push_back(dp[i-1][y][1] -pref[y][0]);
////// //cout << ant.back() << ' ';
}
// //// //cout << '\n';
rmq[0].build(ant);
for(int y = 0;y <= n;y++){
dp[i][y][1] = max({rmq[0].query(0, y)+pref[y][0], dp[i-1][y][2], dp[i-1][y][3]});
//cout << dp[i][y][1] << ' ';
}
//cout << '\n';
ant.clear();
for(int y = 0;y <= n;y++){
ant.push_back(dp[i-1][y][0]);
}
rmq[0].build(ant);
for(int y = 0;y <= n;y++){
dp[i][y][2] = rmq[0].query(0, y);
//cout << dp[i][y][2] << ' ';
}
//cout << '\n';
ant.clear();
for(int y = 0;y <= n;y++){
ant.push_back(dp[i-1][y][0]+pref[y][1]);
}
rmq[0].build(ant);
for(int y = 0;y <= n;y++){
dp[i][y][3] = rmq[0].query(y, n)- pref[y][1];
//cout << dp[i][y][3] << ' ';
}
//cout << '\n';
}
return dp[n][0][0];
}
