#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
int n = N, m = M;
for (int i = 0; i < m; i++){
X[i]++; Y[i]++;
}
vector<int> d[n + 1];
for (int i = 0; i < m; i++){
d[X[i]].pb(i);
}
vector<vector<ll>> F(n + 1, vector<ll>(n + 1));
for (int i = 1; i <= n; i++){
for (int j: d[i]){
F[i][Y[j]] = W[j];
}
for (int j = 1; j <= n; j++){
F[i][j] += F[i][j - 1];
}
}
auto f = [&](int i, int l, int r){
return F[i][r] - F[i][l - 1];
};
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + 1, vector<ll>(2)));
for (int i = 2; i <= n; i++){
for (int j = 0; j <= n; j++){
// dp[i][j][0]
for (int k = 0; k <= j; k++){
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] + f(i - 1, k + 1, j));
}
if (i > 2){
for (int t = 0; t <= j; t++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i - 2][t][0], dp[i - 2][t][1]) + f(i - 1, 1, j));
}
for (int t = j + 1; t <= n; t++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i - 2][t][0], dp[i - 2][t][1]) + f(i - 1, 1, t));
}
}
// dp[i][j][1]
for (int k = j + 1; k <= n; k++){
dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][k][0], dp[i - 1][k][1]) + f(i, j + 1, k));
}
}
}
ll out = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++){
out = max({out, dp[i][j][0], dp[i][j][1]});
}
}
return out;
}
