#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (int)(1e18)
const int N = 3005;
long long a[N][N];
long long dp[N][N][2];
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
if (n > 3000) return 0LL;
for (int i = 0; i < m; i++){
a[x[i] + 1][y[i] + 1] = w[i];
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
a[i][j] += a[i][j - 1];
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
dp[i][j][0] = dp[i][j][1] = -INF;
}
}
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++){
//dp[i][j][0] = value with j as last and on increasing part of bitonic sequence / before was 0
//start a bitonic sequence here using the previous column
for (int j = 1; j <= n; j++){
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][0][0] + a[i - 1][j] - a[i][j]);
}
//start a bitonic sequence by interloping from one before
if (i >= 2){
long long mx = -INF;
for (int j = 1; j <= n; j++) mx = max(mx, dp[i - 2][j][1]);
for (int j = 1; j <= n; j++){
dp[i][j][0] = max(dp[i][j][0], mx - a[i][j]);
}
}
//extend bitonic sequence in increasing first time
long long best = -INF;
for (int j = 1; j <= n; j++){
best = max(best, dp[i - 1][j][0]);
dp[i][j][0] = max(dp[i][j][0], best + a[i - 1][j] - a[i][j]);
}
//extend bitonic sequence in decreasing
best = -INF;
for (int j = n; j >= 1; j--){
best = max(best, dp[i - 1][j][1]);
dp[i][j][1] = max(dp[i][j][1], best + a[i + 1][j] - a[i][j]);
}
//0-->1 transformation
for (int j = 1; j <= n; j++){
dp[i][j][1] = max(dp[i][j][1], dp[i][j][0] + a[i][j] + a[i + 1][j]);
}
//end bitonic sequence now
for (int j = 1; j <= n; j++){
dp[i][0][0] = max(dp[i][0][0], dp[i - 1][j][1] - a[i][j]);
if (i >= 2) dp[i][0][0] = max(dp[i][0][0], dp[i - 2][j][1]);
}
dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][0]);
}
long long ans = -INF;
for (int j = 0; j <= n; j++){
ans = max(ans, dp[n][j][0]);
ans = max(ans, dp[n][j][1]);
}
return ans;
}
// int main(){
// int n, m; cin >> n >> m;
// vector <int> a(m), b(m), c(m);
// for (auto &x : a) cin >> x;
// for (auto &x : b) cin >> x;
// for (auto &x : c) cin >> x;
// cout << max_weights(n, m, a, b, c) << "\n";
// return 0;
// }
