#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define cout if(0) cout
const int mxN = 300;
ll dp[mxN][10][10][10];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<vector<ll>> prefix(N, vector<ll>(N, 0));
// prefix[i][j] = suma de todos los catfish de la columna i hasta fila j
for (int i=0; i<M; i++) {
prefix[X[i]][Y[i]]=W[i];
}
for (int i=0; i<N; i++) {
for (int j=1; j<N; j++) {
prefix[i][j] += prefix[i][j-1];
}
}
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
for (int k=0; k<10; k++) {
dp[0][i][j][k] = 0;
}
}
}
vector<vector<ll>> mx(10, vector<ll>(10, 0));
for (int i=1; i<N; i++) {
cout << i << endl;
for (int j=0; j<10; j++) {
for (int k1=0; k1<10; k1++) {
for (int k2=0; k2<10; k2++) {
dp[i][j][k1][k2] = mx[k1][k2];
//if (j == 0 && k1 == 5 && k2 == 0) cout << mx[k1][k2] << endl;
}
}
}
cout << i << endl;
vector<vector<ll>> newmx(10, vector<ll>(10, 0));
for (int j=0; j<10; j++) {
for (int k1=0; k1<10; k1++) {
for (int k2=0; k2<10; k2++) {
if (max(j, k2) > N || k1 > N) continue;
int mn = (i == 1 ? j : min(j, k2));
ll sum = (mn > 0 ? prefix[i-1][mn-1] : 0);
sum -= (k1 > 0 ? prefix[i-1][k1-1] : 0);
sum = max(0ll, sum);
dp[i][j][k1][k2] = max(dp[i][j][k1][k2], sum+mx[k1][k2]);
//if (j == 5 && k1 == 0) cout << mx[j][k1] << endl;
cout << j << " " << k1 << " " << k2 << " " << dp[i][j][k1][k2] << endl;
newmx[j][k1] = max(newmx[j][k1], dp[i][j][k1][k2]);
}
}
}
mx = newmx;
}
ll ans = 0;
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
for (int k=0; k<10; k++) {
if (max(i, j) > N || k > N) continue;
ans = max(ans, dp[N-1][i][j][k]);
}
}
}
return ans;
}
