#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define f0(i, n) for(int i = 0; i < (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define pb push_back
#define ff first
#define ss second
typedef vector<int> vi;
typedef long long ll;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
bool allxeven = true;
bool allxleq1 = true;
bool ally0 = true;
f0(i, M) {
if(X[i] % 2 == 1) allxeven = false;
if(X[i] > 1) allxleq1 = false;
if(Y[i] != 0) ally0 = false;
}
if (allxeven) {
ll ret = 0;
f0(i, M) ret += W[i];
return ret;
}
if(allxleq1) {
ll ret = 0;
ll ans = 0;
int arr[N][2];
f0(i, N) arr[i][0] = 0, arr[i][1] = 0;
f0(i, M) {
arr[Y[i]][X[i]] = W[i];
}
if(N == 2) {
return max(arr[0][0] + arr[1][0], arr[0][1] + arr[1][1]);
}
f0(i, N) {
ans += arr[i][1];
}
ret = ans;
f0(i, N) {
ans -= arr[i][1];
ans += arr[i][0];
ret = max(ret, ans);
}
return ret;
}
if(ally0) {
int arr[N];
f0(i, N) arr[i] = 0;
f0(i, M) arr[X[i]] = W[i];
ll dp[N][4];
dp[0][0] = -1e18;
dp[0][1] = -1e18;
dp[0][2] = 0;
dp[0][3] = arr[0];
dp[1][0] = 0;
dp[1][1] = arr[1];
dp[1][2] = arr[0];
dp[1][3] = -1e18;
f1(i, N-2) {
dp[i+1][0] = max(dp[i][0], dp[i][2]);
dp[i+1][1] = max(dp[i][0], dp[i][2]) + arr[i+1];
dp[i+1][2] = max(dp[i][1], dp[i][3]);
dp[i+1][3] = dp[i][1] + arr[i+1];
}
return max({
dp[N-1][0],
dp[N-1][1],
dp[N-1][2]
});
}
ll arr[N][10];
f0(i, N) f0(j, 10) arr[i][j] = 0;
f0(i, M) {
arr[X[i]][Y[i]+1] = W[i];
}
ll prefarr[N][10];
f0(i, N) prefarr[i][0] = 0;
f0(i, N) f1(j, 9) {
prefarr[i][j] = prefarr[i][j-1] + arr[i][j];
}
ll dp[N][10][10][10];
ll mxdp[N][10][10];
f0(i, 10) f0(j, 10) {
f0(k, 10) dp[0][i][j][k] = 0;
mxdp[0][i][j] = 0;
}
f0(i, 10) f0(j, 10) {
ll val = 0;
if(i > j) {
for(int x = j+1; x <= i; x++) val += arr[0][x];
} else {
for(int x = i+1; x <= j; x++) val += arr[1][x];
}
mxdp[1][i][j] = val;
f0(k, 10) {
dp[1][i][j][k] = val;
}
}
f1(col, N-2) {
f0(i, 10) f0(j, 10) {
ll mx = 0;
f0(k, 10) {
dp[col+1][i][j][k] = mxdp[col][j][k];
if(max(j, k) <= i) {
dp[col+1][i][j][k] += prefarr[col][i] - prefarr[col][max(j, k)];
}
if(j >= i) dp[col+1][i][j][k] += prefarr[col+1][j] - prefarr[col+1][i];
mx = max(mx, dp[col+1][i][j][k]);
}
mxdp[col+1][i][j] = mx;
// cout << mx << endl;
}
}
ll ans = 0;
f0(i, 10) f0(j, 10) ans = max(ans, mxdp[N-1][i][j]);
return ans;
return 9;
}
