#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 3e2 + 10;
const int mod = 1e9 + 7;
int n, m;
long long D[N][N], f[2][N][N];
long long max_weights(int N, int M,std::vector<int> X ,std::vector<int> Y ,std::vector<int> W )
{
n = N;
m = M;
for(int i = 0;i < m; i++) {
X[i]++;
Y[i]++;
D[X[i]][Y[i]] = 1ll * W[i];
}
memset(f,-61,sizeof(f));
for(int i = 1;i <= n; i++) f[0][1][i] = f[1][1][i] = 0;
for(int i = 2;i <= n; i++) {
//
long long sum = 0;
for(int j = 0;j <= n; j++) {
sum += D[i][j];
f[0][i - 1][j] += sum;
f[1][i - 1][j] += sum;
}
for(int j = 0;j <= n; j++) {
for(int e = 0;e <= j - 1; e++) f[0][i - 1][e] += D[i - 1][j];
for(int e = j;e <= n; e++) f[0][i - 1][e] -= D[i][j];
for(int e = 0;e <= n; e++) {
if(e <= j) f[0][i][j] = max(f[0][i][j],f[0][i - 1][e]);
else f[1][i][j] = max(f[1][i][j],f[0][i - 1][e]);
}
}
for(int j = 0;j <= n; j++) {
for(int e = j;e <= n; e++) f[1][i - 1][e] -= D[i][j];
for(int e = 0;e <= n; e++) {
if(e <= j) f[0][i][j]= max(f[0][i][j], f[1][i - 1][e]);
else f[1][i][j] = max(f[1][i][j], f[1][i - 1][e]);
}
}
}
long long kq = 0;
for(int i = 0;i <= n; i++) kq = max({kq, f[0][n][i], f[1][n][i]});
return kq;
}
