#include "fish.h"
#include <vector>
#include <iostream>
using namespace std;
long long mat[100005][5];
long long spar[100005][5];
long long dp[100005][5][5];
long long cost(int col, int a, int b, int c)
{
long long sum = 0;
if (c >= b && c >= a)
{
sum += spar[col - 1][c] - spar[col - 1][max(a, b)];
}
else if (c >= a)
{
sum -= spar[col - 1][c] - spar[col - 1][a];
}
if (c > b)
{
sum -= spar[col][b];
}
else
{
sum -= spar[col][b];
}
sum += spar[col + 1][c];
return sum;
}
long long inf = 1e16;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
int n = N, m = M;
int ymax = 0;
for(int i=0; i<=n+1; i++)
{
for(int j=0; j<=n+1; j++)
{
mat[i][j]=0;
}
}
for (int i = 0; i < m; i++)
{
mat[X[i] + 1][Y[i] + 1] = W[i];
ymax = max(ymax, Y[i] + 1);
}
for (int col = 0; col <= n+1; col++)
{
for (int lin = 1; lin <= ymax; lin++)
{
spar[col][lin] += spar[col][lin - 1] + mat[col][lin];
}
}
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= ymax; j++)
{
for (int z = 0; z <= ymax; z++)
{
dp[i][j][z] = -inf;
}
}
}
dp[0][0][0] = 0;
long long maxim = 0;
for (int i = 1; i <= n; i++)
{
for (int c = 0; c <= ymax; c++)
{
for (int b = 0; b <= ymax; b++)
{
for (int a = 0; a <= ymax; a++)
{
dp[i][b][c] = max(dp[i][b][c], dp[i - 1][a][b] + cost(i, a, b, c));
maxim = max(maxim, dp[i][b][c]);
}
//cout<<i<<" "<<b<<" "<<c<<" "<<dp[i][b][c]<<'\n';
}
}
}
return maxim;
}
