#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m;
long long val[3005][3005], pref[3005][3005];
// dp[row_i][row_j][i - 1 > or = or <]
long long dp[3005][3005][2];
ll x[N], y[N], w[N];
ll solve1(){
ll tol = 0;
for(int i = 1; i <= m; i++) tol += w[i];
return tol;
}
map<ii, ll> mp;
ll solve2(){
for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
if(n >= 3){
ll mx = -1, total = 0;
for(int i = 1; i <= n; i++) total += mp[{2, i}];
mx = total;
for(int i = 1; i <= n; i++){
total += (mp[{1, i}] - mp[{2, i}]);
mx = max(mx, total);
}
return mx;
}
else{
return max(mp[{1, 1}] + mp[{1, 2}], mp[{2, 1}] + mp[{2, 2}]);
}
}
ll dp1[N][2][2];
ll solve3(){
//cout << "OK\n";
for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++) dp1[i][j][k] = -oo;
}
}
dp1[1][0][0] = dp1[1][1][0] = 0;
for(int i = 2; i <= (n + 1); i++){
for(int j = 0; j < 2; j++){
if(i == (n + 1) && j) break;
for(int k = 0; k < 2; k++){
for(int h = 0; h < 2; h++){
dp1[i][j][k] = max(dp1[i][j][k], dp1[i - 1][k][h] + mp[{i - 1, 1}] * (!k && (j | h)));
}
//cout << i << " " << j << " " << k << " " << dp1[i][j][k] << "\n";
}
}
}
return max(dp1[n + 1][0][0], dp1[n + 1][0][1]);
}
long long max_weights(int _n, int _m, vector<int> _x, vector<int> _y, vector<int> _w){
n = _n, m = _m;
bool chk1 = 1, chk2 = 1, chk3 = 1;
for(int i = 0; i < m; i++){
x[i + 1] = _x[i] + 1, y[i + 1] = _y[i] + 1, w[i + 1] = _w[i];
chk1 &= (!(_x[i] & 1));
chk2 &= (_x[i] <= 1);
chk3 &= (_y[i] <= 0);
if(n <= 3000) val[_x[i] + 1][_y[i] + 1] += (long long)_w[i];
}
if(n <= 3000){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) pref[i][j] = pref[i][j - 1] + val[i][j];
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
dp[i][j][0] = dp[i][j][1] = -oo;
}
}
//dp[0][0][0] = 0;
//15206896898496
for(int i = 0; i <= n; i++){
//dp[2][i][0] = pref[1][i];// 0 -> <=
//dp[2][i][1] = pref[2][i;
dp[1][i][0] = 0;
}
for(int i = 2; i <= n + 1; i++){
// calculate (i - 1)
long long maximum = -oo;
for(int nxt = 0; nxt <= n; nxt++){
maximum = max(maximum, dp[i - 1][nxt][0] - pref[i - 1][nxt]);
dp[i][nxt][0] = max(dp[i][nxt][0], maximum + pref[i - 1][nxt]);
}
maximum = -oo;
for(int nxt = n; nxt >= 0; nxt--){
dp[i][nxt][1] = max(dp[i][nxt][1], maximum - pref[i][nxt]);
maximum = max(maximum, dp[i - 1][nxt][1] + pref[i][nxt]);
}
for(int lst = 0; lst <= n; lst++){
// 0 - 0
/*
for(int nxt = lst; nxt <= n; nxt++){
dp[i][nxt][0] = max(dp[i][nxt][0], dp[i - 1][lst][0] + (pref[i - 1][nxt] - pref[i - 1][lst]));
}
// 1 - 1
for(int nxt = lst - 1; nxt >= 0; nxt--){
dp[i][nxt][1] = max(dp[i][nxt][1], dp[i - 1][lst][1] + pref[i][lst] - pref[i][nxt]);
}*/
// 0 - 1
if(lst == n){
for(int nxt = 0; nxt < n; nxt++) dp[i][nxt][1] = max(dp[i][nxt][1], dp[i - 1][n][0] + pref[i][n] - pref[i][nxt]);
}
// 1 - 0
if(!lst){
dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][1]);
for(int nxt = 1; nxt <= n; nxt++) dp[i][nxt][0] = max(dp[i][nxt][0], max(dp[i - 1][0][0] + pref[i - 1][nxt], dp[i - 1][0][1]));
}
}
}
return max(dp[n + 1][0][0], dp[n + 1][0][1]);
}
else if(chk1) return solve1();
else if(chk2) return solve2();
else if(chk3) return solve3();
}
/*
void process(){
int n, m;
vector<int> a, b, c;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
a.pb(x), b.pb(y), c.pb(z);
}
cout << max_weights(n, m, a, b, c) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
freopen("fish.inp", "r", stdin);
//freopen("fish.out", "w", stdout);
//cout << "OK\n";
//return 0;
process();
}
*/
